C语言 找到给定数字的因数的算法.. 最短方法？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/2844703/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Algorithm to find the factors of a given Number.. Shortest Method?
提问by AGeek
What could be the simplest and time efficient logic to find out the factors of a given Number. Is there any algorithm that exist, based on the same.
找出给定数字的因数的最简单且省时的逻辑是什么？是否存在任何基于相同的算法。
Actually, my real problem is to find out the no. of factors that exist for a given Number..
实际上，我真正的问题是找出编号。存在给定数字的因素的数量..
So Any algorithm, please let me know on this..
所以任何算法，请让我知道这个..
Thanks.
谢谢。
回答by IVlad
Actually, my real problem is to find out the no. of factors that exist for a given Number..
实际上，我真正的问题是找出编号。存在给定数字的因素的数量..
Well, this is different. Let nbe the given number.
嗯，这是不同的。让n是给定的数字。
If n = p1^e1 * p2^e2 * ... * pk^ek, where each pis a prime number, then the number of factors of nis (e1 + 1)*(e2 + 1)* ... *(ek + 1). More on this here.
如果n = p1^e1 * p2^e2 * ... * pk^ek，其中每个p都是素数，则 的因数数n是(e1 + 1)*(e2 + 1)* ... *(ek + 1)。更多关于这个在这里。
Therefore, it is enough to find the powers at which each prime factor appears. For example:
因此，找到每个素因数出现的幂就足够了。例如：
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
}
For example, take 18. 18 = 2^1 * 3*2 => number of factors = (1 + 1)*(2 + 1) = 6. Indeed, the 6factors of 18are 1, 2, 3, 6, 9, 18.
例如，取18. 18 = 2^1 * 3*2 => number of factors = (1 + 1)*(2 + 1) = 6. 确实， 的6因素18是1, 2, 3, 6, 9, 18。
Here's a little benchmark between my method and the method described and posted by @Maciej. His has the advantage of being easier to implement, while mine has the advantage of being faster if change to only iterate over the prime numbers, as I have done for this test:
这是我的方法与@Maciej 描述和发布的方法之间的一个小基准。他的优点是更容易实现，而我的优点是如果更改为仅迭代素数，则速度更快，正如我在此测试中所做的那样：
class Program
{
static private List<int> primes = new List<int>();
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);
}
}
Results on my machine:
我机器上的结果：
Testing equivalence...
Equivalence confirmed!
Timing IVlad...
Total milliseconds: 2448
Timing Maciej...
Total milliseconds: 3951
Press any key to continue . . .
测试等效性...
等效性确认！
计时 IVlad...
总毫秒数：2448
计时 Maciej...
总毫秒数：3951
按任意键继续。. .
回答by Daniel Brückner
There is a large number of algorithms available - from simple trial devision to very sophisticated algorithms for large numbers. Have a look at Integer Factorizationon Wikipedia and pick one that suits your needs.
有大量可用的算法——从简单的试验设计到非常复杂的大量算法。看看维基百科上的整数因式分解，然后选择一个适合你的需求。
Here is a short but inefficient C# implementation that finds the number of prime factors. If you need the number of factors (not prime factors) you have to store the prime factors with their multiplicity and calculate the number of factors afterwards.
这是一个简短但效率低下的 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++;
}
}
回答by Maciej Hehl
Here is a fruit of my short discussion with |/|ad :)
这是我与 |/|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;
}
回答by Darin Dimitrov
You may take a look at this algorithm.
你可以看看这个算法。
回答by Ajay
Careful, this answer is not useful/fast for a single value of n.
小心，这个答案对于 n 的单个值没有用/快速。
Method 1:
方法一：
You can get it in O(polylog(n)) if you maintain a look-up table (for the first prime factor of a number).
如果你维护一个查找表（对于一个数字的第一个素数），你可以在 O(polylog(n)) 中得到它。
If gcd(a,b) == 1, then no. of factors of a*b = (no. of factors of a) * (no. of factors of b)
如果 gcd(a,b) == 1，则否。a*b 的因子数 =（a 的因子数）*（b 的因子数）
Therefore, for a given number a*b, if gcd(a,b) != 1 then we can have two other numbers p and q where p = a and q = b/gcd(a,b). Thus, gcd(p,q) == 1. Now, we can recursively find the number of factors for p and q.
因此，对于给定的数字 a*b，如果 gcd(a,b) != 1 那么我们可以有另外两个数字 p 和 q，其中 p = a 和 q = b/gcd(a,b)。因此，gcd(p,q) == 1。现在，我们可以递归地找到 p 和 q 的因子数。
It will take only some small amount of efforts to ensure neither p nor q is 1.
只需少量的努力即可确保 p 和 q 都不为 1。
P.S. This method is also useful when you need to know the number of factors of all numbers from 1 to n. It would be an order of O(nlogn + O(look-up table)).
PS 当你需要知道从 1 到 n 的所有数的因数的个数时，这个方法也很有用。这将是 O(nlogn + O(look-up table)) 的顺序。
Method 2: (I do not have ownership for this.)
方法 2:(我没有这个所有权。）
If you have the look-up for first prime factor till n, then you can know it's all prime factors in O(logn) and thus find the number of factors from them.
如果您在 n 之前查找第一个质因子，那么您可以知道它是 O(logn) 中的所有质因子，从而从中找到因子的数量。
P.S. Google 'Factorization in logn' for better explanation.
PS Google 'Factorization in logn' 以获得更好的解释。
回答by joejoeson
Euclid's Algorithm should suffice.
欧几里德算法应该足够了。
