Функция c# принимает целое число n и возвращает наименьшее число, которое может делить числа 1..n

Question 1

Мне нужно написать функцию, которая принимает в качестве аргумента число n и возвращает (в виде строки) наименьшее доступное число, которое можно разделить на все числа от 1 до n. пример, если n=4, то функция вернет 12, так как 12/4, 12/3, 12/2, 12/1-это целые числа.

я написал для этого функцию, которая отлично работает, когда числа меньше 19.. выше 19, вычислительное время становится намного больше. может ли кто-нибудь дать мне подсказку, как улучшить механизм этой функции, чтобы сделать это быстрее

 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

У вас будут огромные цифры для больших n, вот почему давайте использовать BigInteger для внутренних вычислений. Как выразился Абхишек Пандей, мы должны вычислить LCM, которые могут быть получены в виде

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

где CGD - Наибольший общий делитель

Код:

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();
}

Демонстрация:

  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));

Результат:

 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

Моя логика:

Мы берем число - это минимальное число, которое можно вернуть
число - 1 - если оно не может разделиться без напоминания, добавьте к n начальное n

Не забудьте обновить номер до начального, когда на 2 шаге появится напоминание

Делайте это до тех пор, пока не получите правильное значение

Question 4

Вам нужно найти LCM (наименьшее общее кратное) всех чисел из 1 to n.

Вот хороший пример для поиска LCM массива элементов. https://www.geeksforgeeks.org/lcm-of-given-array-elements/

Вы можете создать массив из всех чисел от 1 до n и передать его этой функции.

или

Вы можете изменить его, чтобы он проходил только n и сделайте его эффективным для вашего случая использования.

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

У вас будут огромные цифры для больших n, вот почему давайте использовать BigInteger для внутренних вычислений. Как выразился Абхишек Пандей, мы должны вычислить LCM, которые могут быть получены в виде

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

где CGD - Наибольший общий делитель

Код:

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();
}

Демонстрация:

  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));

Результат:

 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

Моя логика:

Мы берем число - это минимальное число, которое можно вернуть
число - 1 - если оно не может разделиться без напоминания, добавьте к n начальное n

Не забудьте обновить номер до начального, когда на 2 шаге появится напоминание

Делайте это до тех пор, пока не получите правильное значение

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

Вам нужно найти LCM (наименьшее общее кратное) всех чисел из 1 to n.

Вот хороший пример для поиска LCM массива элементов. https://www.geeksforgeeks.org/lcm-of-given-array-elements/

Вы можете создать массив из всех чисел от 1 до n и передать его этой функции.

или

Вы можете изменить его, чтобы он проходил только n и сделайте его эффективным для вашего случая использования.

Функция c# принимает целое число n и возвращает наименьшее число, которое может делить числа 1..n

Вопрос

Лучший ответ

На других языках

Эта страница на других языках

Популярное в этой категории

Популярные вопросы в этой категории