实际上，我真正的问题是找出编号。给定数字存在的因素
好吧，这是不同的。设n给定数字。
如果n = p1^e1 * p2^e2 * ... * pk^ek，其中每个p都是质数，则的因子个数n为(e1 + 1)*(e2 + 1)*... *(ek + 1)。更多关于此这里。
因此，找到每个素因出现的幂就足够了。例如：
read given number in ninitial_n = nnum_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因子的最简单，最省时的逻辑是什么？是否存在基于该算法的算法？
实际上，我真正的问题是找出编号。给定数字存在的因素
所以任何算法，请让我知道。
谢谢。
