c#函式接受整數n并回傳可以除以數字1..n的最小數-有解無憂

我需要撰寫一個函式，該函式將數字 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  ;
            }

        }

uj5u.com熱心網友回復：

我的邏輯：

我們取一個數字 - 它是可以回傳的最小數字
number - 1 - 如果它不能在沒有提醒的情況下除以添加到 n 初始 n

2 步有提醒時不要忘記將數字更新為首字母

這樣做直到你得到正確的值

uj5u.com熱心網友回復：

您需要從中找到所有數字的 LCM（最低公倍數）1 to n。

這是查找元素陣列的 LCM 的一個很好的示例。 https://www.geeksforgeeks.org/lcm-of-given-array-elements/

您可以創建一個包含從 1 到 n 的所有數字的陣列，并將其傳遞給此函式。

或者

您可以將其修改為僅通過n并使其對您的用例有效。

uj5u.com熱心網友回復：

您將有大量的 large 數字n，這就是為什么讓我們BigInteger用于內部計算。正如 Abhishek Pandey 所說，我們應該計算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

轉載請註明出處，本文鏈接：https://www.uj5u.com/gongcheng/364324.html

標籤：C＃算法

上一篇：如何在不使用numpy的情況下計算python中的標準偏差？

下一篇：如何撰寫決議器來構造運算式ab[cd][e].f[g[h[ij]]]的JavaScriptASTMemberExpression？