我正在尝试重构此算法以使其更快。为了速度，这里的第一个重构是什么？
public int GetHowManyFactors(int numberToCheck)
{
// we know 1 is a factor and the numberToCheck
int factorCount = 2;
// start from 2 as we know 1 is a factor, and less than as numberToCheck is a factor
for (int i = 2; i < numberToCheck; i++)
{
if (numberToCheck % i == 0)
factorCount++;
}
return factorCount;
}
您可以进行的第一个优化是您只需要检查数字的平方根。这是因为因子成对出现，其中一个小于平方根，另一个大于平方根。
一个例外是如果n是一个精确的平方，那么它的平方根是一个因子，n但不是一对的一部分。
例如，如果您的号码是 30，则这些因素在这些对中：
因此，您无需检查任何大于 5 的数字，因为一旦您在该对中找到相应的小因子，就可以推断出所有其他因子存在。
这是在 C# 中执行此操作的一种方法：
public int GetFactorCount(int numberToCheck)
{
int factorCount = 0;
int sqrt = (int)Math.Ceiling(Math.Sqrt(numberToCheck));
// Start from 1 as we want our method to also work when numberToCheck is 0 or 1.
for (int i = 1; i < sqrt; i++)
{
if (numberToCheck % i == 0)
{
factorCount += 2; // We found a pair of factors.
}
}
// Check if our number is an exact square.
if (sqrt * sqrt == numberToCheck)
{
factorCount++;
}
return factorCount;
}
您可以使用其他更快的方法，但您可能会发现这已经足够快以满足您的需求，特别是如果您只需要它来处理 32 位整数。
减少你必须走多高的界限，因为你可以有意识地停在数字的平方根处，尽管这确实需要谨慎选择具有奇数个因子的正方形，但它确实有助于减少频率必须执行循环。
从 2（如果您的数字是偶数）或 3（对于奇数）开始循环计数器。这应该允许您检查每个其他数字，将循环计数再减少 50%。
public int GetHowManyFactors(int numberToCheck)
{
// we know 1 is a factor and the numberToCheck
int factorCount = 2;
int i = 2 + ( numberToCheck % 2 ); //start at 2 (or 3 if numberToCheck is odd)
for( ; i < numberToCheck / 2; i+=2)
{
if (numberToCheck % i == 0)
factorCount++;
}
return factorCount;
}
看起来这里有一个关于这个确切主题的冗长讨论：Algorithm to calculate the number of divisors of a given number
希望这可以帮助
首先要注意的是，找到所有主要因素就足够了。一旦你有了这些，就很容易找到总除数的数量：对于每个素数，将其出现的次数加 1 并将它们相乘。所以对于 12 = 2 * 2 * 3 你有 (2 + 1) * (1 + 1) = 3 * 2 = 6 个因子。
接下来的事情是从第一件事开始：当你找到一个因素时，把它分开，这样得到的数字就会更小。当您将这一点与您只需要检查当前数字的平方根这一事实结合起来时，这是一个巨大的改进。例如，考虑 N = 10714293844487412。天真地它需要 N 步。检查其平方根需要 sqrt(N) 或大约 1 亿步。但是由于因子 2、2、3 和 953 是在早期发现的，因此您实际上只需要检查到一百万——提高了 100 倍！
另一个改进：您不需要检查每个数字是否将其除以您的数字，只需检查素数即可。如果更方便，您可以使用 2 和奇数，或 2、3 和数字 6n-1 和 6n+1（基本轮筛）。
这是另一个不错的改进。如果您可以快速确定一个数是否为素数，则可以进一步减少除法的需要。假设去除小因素后，你有 120528291333090808192969。即使检查到它的平方根也需要很长时间——3000 亿步。但是米勒拉宾测试（非常快 - 可能是 10 到 20纳秒) 将表明这个数字是复合的。这有什么帮助？这意味着如果你检查它的立方根并且没有找到任何因子，那么就剩下两个素数了。如果数是正方形，它的因数是素数；如果数字不是正方形，则数字是不同的素数。这意味着您可以将您的“运行总数”分别乘以 3 或 4，以获得最终答案——即使不知道这些因素！这比您想象的要大得多：所需的步骤数从 3000 亿下降到 5000 万，提高了 6000 倍！
以上唯一的问题是米勒-拉宾只能证明数字是复合的；如果给定一个素数，则无法证明该数字是素数。在这种情况下，您可能希望编写一个素数证明函数来省去因式分解数的平方根的工作。（或者，如果您对自己的答案是正确的而不是证明它的证明感到满意，那么您可以只做更多的 Miller-Rabin 测试。如果一个数字通过 15 次测试，那么它是复合概率小于 1十亿。）
好吧，如果您要经常使用此功能，则可以使用 Eratosthenes http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes的修改算法，并将间隔 1 到 Max 的答案存储在数组中。它将运行 IntializeArray() 一次，然后在 0(1) 中返回答案。
const int Max =1000000;
int arr [] = new int [Max+1];
public void InitializeArray()
{
for(int i=1;i<=Max;++i)
arr[i]=1;//1 is factor for everyone
for(int i=2;i<=Max;++i)
for(int j=i;i<=Max;i+=j)
++arr[j];
}
public int GetHowManyFactors(int numberToCheck)
{
return arr[numberToCheck];
}
但是如果你不打算经常使用这个功能，我认为最好的解决方案是检查 unitll 平方根。
注意：我已经更正了我的代码！
Pollard Rho是一种易于实现的算法，它可以让您比试用部门走得更远
这是一个 Java 实现，应该很容易适应 C#：http ://www.cs.princeton.edu/introcs/78crypto/PollardRho.java.html
https://codility.com/demo/results/demoAAW2WH-MGF/
public int solution(int n) {
var counter = 0;
if (n == 1) return 1;
counter = 2; //1 and itself
int sqrtPoint = (Int32)(Math.Truncate(Math.Sqrt(n)));
for (int i = 2; i <= sqrtPoint; i++)
{
if (n % i == 0)
{
counter += 2; // We found a pair of factors.
}
}
// Check if our number is an exact square.
if (sqrtPoint * sqrtPoint == n)
{
counter -=1;
}
return counter;
}
Codility Python 100 % 这是python中的解决方案，几乎没有解释-
def solution(N):
"""
Problem Statement can be found here-
https://app.codility.com/demo/results/trainingJNNRF6-VG4/
Codility 100%
Idea is count decedent factor in single travers. ie. if 24 is divisible by 4 then it is also divisible by 8
Traverse only up to square root of number ie. in case of 24, 4*4 < 24 but 5*5!<24 so loop through only i*i<N
"""
print(N)
count = 0
i = 1
while i * i <= N:
if N % i == 0:
print()
print("Divisible by " + str(i))
if i * i == N:
count += 1
print("Count increase by one " + str(count))
else:
count += 2
print("Also divisible by " + str(int(N / i)))
print("Count increase by two count " + str(count))
i += 1
return count
运行示例-
if __name__ == '__main__':
# result = solution(24)
# result = solution(35)
result = solution(1)
print("")
print("Solution " + str(result))
""" 示例 1- 24
能被 1 整除 也能被 24 整除 计数增加 2 计数 2
能被 2 整除 也能被 12 整除 计数增加 2 计数 4
能被 3 整除 也能被 8 整除 计数增加 2 计数 6
能被 4 整除 也能被 6 整除 计数增加 2 计数 8
解决方案 8
示例 2- 35
能被 1 整除 也能被 35 整除 计数增加 2 计数 2
能被 5 整除 也能被 7 整除 计数增加 2 计数 4
解决方案 4
示例 3-
1
可被 1 整除 计数加一 1
解决方案 1 """
我得到了非常好的结果，复杂度为 O(sqrt(N))。
if (N == 1) return 1;
int divisors = 0;
int max = N;
for (int div = 1; div < max; div++) {
if (N % div == 0) {
divisors++;
if (div != N/div) {
divisors++;
}
}
if (N/div < max) {
max = N/div;
}
}
return divisors;
Python 实现分数 100% https://app.codility.com/demo/results/trainingJ78AK2-DZ5/
import math;
def solution(N):
# write your code in Python 3.6
NumberFactor=2; #one and the number itself
if(N==1):
return 1;
if(N==2):
return 2;
squareN=int(math.sqrt(N)) +1;
#print(squareN)
for elem in range (2,squareN):
if(N%elem==0):
NumberFactor+=2;
if( (squareN-1) * (squareN-1) ==N):
NumberFactor-=1;
return NumberFactor