查找给定数字因子的算法。最短方法？
实际上，我真正的问题是找出编号。给定数字存在的因素
好吧，这是不同的。设n给定数字。
如果n = p1^e1 * p2^e2 * ... * pk^ek，其中每个p都是质数，则的因子个数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。确实，的6因素18是1, 2, 3, 6, 9, 18。
这是我的方法与@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);
}
}
我的机器上的结果：
测试等效项… 等效项已确认！ Timing IVlad … 总毫秒数：2448 Timing Maciej … 总毫秒数：3951 按任意键继续。。。
找出给定Number因子的最简单，最省时的逻辑是什么？是否存在基于该算法的算法？
实际上，我真正的问题是找出编号。给定数字存在的因素
所以任何算法，请让我知道。
谢谢。
你可能想看：