找到给定数字因子的算法..最短方法?
找出给定数字的因子可能是最简单和最有效的逻辑。 是否存在基于相同的算法。
实际上,我真正的问题是找出答案。 对于给定数字存在的因素..
所以任何算法,请告诉我这个..
谢谢。
实际上,我真正的问题是找出答案。 对于给定数字存在的因素..
嗯,这是不同的。 设n
是给定的数字。
如果n = p1^e1 * p2^e2 * ... * pk^ek
,其中每个p
是素数,那么n
的因子n
是(e1 + 1)*(e2 + 1)* ... *(ek + 1)
。 更多关于这里 。
因此,足以找到每个素因子出现的权力。 例如:
read given number in n initial_n = n num_factors = 1; for (i = 2; i * i <= initial_n; ++i) // for each number i up until the square root of the given number { power = 0; // suppose the power i appears at is 0 while (n % i == 0) // while we can divide n by i { n = n / i // divide it, thus ensuring we'll only check prime factors ++power // increase the power i appears at } num_factors = num_factors * (power + 1) // apply the formula } if (n > 1) // will happen for example for 14 = 2 * 7 { num_factors = num_factors * 2 // n is prime, and its power can only be 1, so multiply the number of factors by 2 }
例如, 18
。 18 = 2^1 * 3*2 => number of factors = (1 + 1)*(2 + 1) = 6
。 实际上, 18
的6
因子是1, 2, 3, 6, 9, 18
。
这是我的方法与@Maciej描述和发布的方法之间的一个小基准。 他的优势在于更容易实现,而我的优势是如果更改只能迭代素数就更快,正如我为此测试所做的那样:
class Program { static private List primes = new List (); private static void Sieve() { bool[] ok = new bool[2000]; for (int i = 2; i < 2000; ++i) // primes up to 2000 (only need up to sqrt of 1 000 000 actually) { if (!ok[i]) { primes.Add(i); for (int j = i; j < 2000; j += i) ok[j] = true; } } } private static int IVlad(int n) { int initial_n = n; int factors = 1; for (int i = 0; primes[i] * primes[i] <= n; ++i) { int power = 0; while (initial_n % primes[i] == 0) { initial_n /= primes[i]; ++power; } factors *= power + 1; } if (initial_n > 1) { factors *= 2; } return factors; } private static int Maciej(int n) { int factors = 1; int i = 2; for (; i * i < n; ++i) { if (n % i == 0) { ++factors; } } factors *= 2; if (i * i == n) { ++factors; } return factors; } static void Main() { Sieve(); Console.WriteLine("Testing equivalence..."); for (int i = 2; i < 1000000; ++i) { if (Maciej(i) != IVlad(i)) { Console.WriteLine("Failed!"); Environment.Exit(1); } } Console.WriteLine("Equivalence confirmed!"); Console.WriteLine("Timing IVlad..."); Stopwatch t = new Stopwatch(); t.Start(); for (int i = 2; i < 1000000; ++i) { IVlad(i); } Console.WriteLine("Total milliseconds: {0}", t.ElapsedMilliseconds); Console.WriteLine("Timing Maciej..."); t.Reset(); t.Start(); for (int i = 2; i < 1000000; ++i) { Maciej(i); } Console.WriteLine("Total milliseconds: {0}", t.ElapsedMilliseconds); } }
在我的机器上的结果:
测试等价......
等价确认了!
时间IVlad ...
总毫秒数:2448
时间Maciej ...
总毫秒数:3951
按任意键继续 。 。 。
有大量的算法可用 – 从简单的试验分割到非常复杂的大数法算法。 查看维基百科上的整数分解 ,并选择一个适合您需求的整数分解 。
这是一个简短但效率低下的C#实现,它可以找到素数因子的数量。 如果您需要多个因子(不是素因子),您必须存储具有多重性的素数因子,然后计算因子的数量。
var number = 3 * 3 * 5 * 7 * 11 * 11; var numberFactors = 0; var currentFactor = 2; while (number > 1) { if (number % currentFactor == 0) { number /= currentFactor; numberFactors++; } else { currentFactor++; } }
你可以看看这个算法 。
这是我与| / | ad :)进行简短讨论的成果
read given number in n int divisorsCount = 1; int i; for(i = 2; i * i < n; ++i) { if(n % i == 0) { ++divisorsCount; } } divisorsCount *= 2; if(i * i == n) { ++divisorsCount; }
小心,这个答案对单个n值没有用/快。
方法1 :
如果你维护一个查找表(对于一个数字的第一个素数因子),你可以在O(polylog(n))中得到它。
如果gcd(a,b)== 1,那么没有。 因子a * b =(a的因子数)*(b的因子数)
因此,对于给定数a * b,如果gcd(a,b)!= 1,那么我们可以有两个其他数p和q,其中p = a和q = b / gcd(a,b)。 因此,gcd(p,q)== 1.现在,我们可以递归地找到p和q的因子数。
只需要做一些小的努力就可以确保p和q都不是1。
PS当您需要知道从1到n的所有数字的因子数时,此方法也很有用。 它将是O的顺序(nlogn + O(查找表))。
方法2 :(我对此没有所有权。)
如果您查找第一个素数因子直到n,那么您可以知道它是O(logn)中的所有主要因子,从而从中找到因子的数量。
PS谷歌’登录中的因子分解’以获得更好的解释。
欧几里德的算法应该足够了。