C# função aceita o inteiro n e retorne o menor número que pode dividir números 1..n

Question 1

Eu preciso escrever uma função que recebe como argumento o número de n e de retorno (como string) o menor número que pode dividir por todos os números de 1 a n. exemplo, se n=4, a função retornará 12 como 12/4 12/3 12/2 12/1 são números inteiros.

eu tenho escrito uma função, pois o que funciona bem quando os números são menos de 19.. acima de 19 a computação de tempo está ficando muito mais tempo. alguém pode me dar uma dica de como melhorar o mecanismo para esta função para fazê-lo mais rápido

 public static string Smallest(int n)
        {
           
            int good = 0;//will hold number of times we got divide with no remianders
            int num = n;//smallest possible number is n
            while (true)
            {
                good = 0;
                for (int i=n; i>=1; i--)
                {
                    if (num % i ==0) good++;//meaning we got zero remainder for the divide
                    if (good == n) return num.ToString();//num of times we got zero remainders == n.

                }
                num++;
            }

        }

Question 2

Você vai ter uma enorme números para grandes n, é por isso que vamos usar BigInteger para o interior de computação. Como Abhishek Pandey colocá-lo, devemos calcular LCM, o que pode ser obtido como

 LCM(a, b) = a * b / GCD(a, b)

onde a CGD é o Maior Divisor Comum

Código:

using System.Numerics;

...

public static string Smallest(int n) {
  if (n < 1)
    throw new ArgumentOutOfRangeException(nameofn()); 

  BigInteger result = 1;

  for (int i = 1; i <= n; ++i) 
    result = result * i / BigInteger.GreatestCommonDivisor(result, i);

  return result.ToString();
}

Demonstração:

  using System.Linq;
  using System.Numerics;

  ...

  var demos = string.Join(Environment.NewLine, Enumerable
    .Range(1, 20)
    .Select(n => $"{n,2} : {Smallest(n),20}"));

  Console.WriteLine(demos);
  Console.WriteLine();
  Console.WriteLine(Smallest(100));

Resultado:

 1 :                    1
 2 :                    2
 3 :                    6
 4 :                   12
 5 :                   60
 6 :                   60
 7 :                  420
 8 :                  840
 9 :                 2520
10 :                 2520
11 :                27720
12 :                27720
13 :               360360
14 :               360360
15 :               360360
16 :               720720
17 :             12252240
18 :             12252240
19 :            232792560
20 :            232792560

69720375229712477164533808935312303556800

Question 3

Minha lógica:

Nós fazemos exame de um número - é o mínimo que pode ser devolvido
número - 1 - se ele não pode dividir com nenhum lembrete adicionar ao n n inicial

Não se esqueça de atualizar o número inicial, quando 2 passo lembrete

Faça isso até você obter o valor correto

Question 4

Você precisa encontrar o LCM (Menor Múltiplo Comum) de todos os números de 1 to n.

Aqui está um bom exemplo para encontrar o mínimo múltiplo comum de uma matriz de elementos. https://www.geeksforgeeks.org/lcm-of-given-array-elements/

Você pode criar uma matriz de todos os números de 1 a n, e passá-lo para essa função.

OU

Você pode modificá-lo para passar apenas n e torná-lo eficiente para o caso de uso.

Dmitry Bychenko · Answer 1 · 2021-11-23T18:37:03

Você vai ter uma enorme números para grandes n, é por isso que vamos usar BigInteger para o interior de computação. Como Abhishek Pandey colocá-lo, devemos calcular LCM, o que pode ser obtido como

 LCM(a, b) = a * b / GCD(a, b)

onde a CGD é o Maior Divisor Comum

Código:

using System.Numerics;

...

public static string Smallest(int n) {
  if (n < 1)
    throw new ArgumentOutOfRangeException(nameofn()); 

  BigInteger result = 1;

  for (int i = 1; i <= n; ++i) 
    result = result * i / BigInteger.GreatestCommonDivisor(result, i);

  return result.ToString();
}

Demonstração:

  using System.Linq;
  using System.Numerics;

  ...

  var demos = string.Join(Environment.NewLine, Enumerable
    .Range(1, 20)
    .Select(n => $"{n,2} : {Smallest(n),20}"));

  Console.WriteLine(demos);
  Console.WriteLine();
  Console.WriteLine(Smallest(100));

Resultado:

 1 :                    1
 2 :                    2
 3 :                    6
 4 :                   12
 5 :                   60
 6 :                   60
 7 :                  420
 8 :                  840
 9 :                 2520
10 :                 2520
11 :                27720
12 :                27720
13 :               360360
14 :               360360
15 :               360360
16 :               720720
17 :             12252240
18 :             12252240
19 :            232792560
20 :            232792560

69720375229712477164533808935312303556800

Andrew · Answer 2 · 2021-11-23T18:29:42

Minha lógica:

Nós fazemos exame de um número - é o mínimo que pode ser devolvido
número - 1 - se ele não pode dividir com nenhum lembrete adicionar ao n n inicial

Não se esqueça de atualizar o número inicial, quando 2 passo lembrete

Faça isso até você obter o valor correto

Abhishek Pandey · Answer 3 · 2021-11-23T18:22:57

Você precisa encontrar o LCM (Menor Múltiplo Comum) de todos os números de 1 to n.

Aqui está um bom exemplo para encontrar o mínimo múltiplo comum de uma matriz de elementos. https://www.geeksforgeeks.org/lcm-of-given-array-elements/

Você pode criar uma matriz de todos os números de 1 a n, e passá-lo para essa função.

OU

Você pode modificá-lo para passar apenas n e torná-lo eficiente para o caso de uso.

C# função aceita o inteiro n e retorne o menor número que pode dividir números 1..n

Pergunta

Melhor resposta

Em outros idiomas

Esta página está em outros idiomas

Popular nesta categoria

Perguntas populares nesta categoria