c# function accept integer n and return lowest number that can divide numbers 1..n-CodePudding

I need to write a function that takes as an argument number n and return (as string) the lowest available number that can divide by all the numbers from 1 to n. example if n=4 then the function will return 12 as 12/4 12/3 12/2 12/1 are whole numbers.

i have written a function for that which works fine when numbers are less than 19.. above 19 the computing time is getting much longer. can someone give me a hint how to better the mechanism for this function to do it quicker

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

        }

CodePudding user response：

My logic:

We take a number - it`s minimal number what can be returned
number - 1 - if it can`t divide with no reminder add to n initial n

Don`t forget to update number to initial when 2 step has reminder

Do this until you get correct value

CodePudding user response：

You need to find the LCM (Lowest Common Multiple) of all the numbers from 1 to n.

Here is a good example to find LCM of an array of elements. https://www.geeksforgeeks.org/lcm-of-given-array-elements/

You can create an array of all the numbers from 1 to n and pass it to this function.

You can modify it to pass only n and make it efficient for your use case.

CodePudding user response：

You are going to have huge numbers for large n, that's why let's use BigInteger for inner computation. As Abhishek Pandey put it, we should compute LCM, which can be obtained as

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

where CGD is the Greatest Common Divisor

Code:

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

Demo:

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

Outcome:

 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