如何用快速的运行时间获得总的非素数

Question

我在一个竞争激烈的编程网站上学习C。问题是，给定一个数字，这个数字有多少非素数？我可以用我的代码这样做：

#include <stdio.h>
int totalNPF(int n){
int totalFactor = 1, temp = 0, primeFactor = 0;
for(int i=2; n!=1;){
while(n % i == 0){
n /= i;
temp++;
}
if(temp != 0){
totalFactor *= (temp+1);
primeFactor ++;
}
i++;
temp = 0;
}
return totalFactor-primeFactor;
}
int main(){
int T, n;
scanf("%d", &T);
for(int i=0; i<T; i++){
scanf("%d", &n);
printf("%dn", totalNPF(n));
}
return 0;
}

我使用了数论的概念，但它仍然很慢。它的运行时间超过1s。有人知道如何提高速度，这样我就可以把速度提高到1秒左右或更低吗？

注意：数字的限制是2x10^6

Answer 1

将for(int i=2; n!=1;){更改为for(int i=2; i*i <= n;){可以使程序更快。一旦n小于当前候选因子的平方，这就终止对因子的搜索。在这一点之后，除了n本身之外，不可能有素因子，因为如果j是大于i的素因子，那么n/j将是小于i的因子。但是这样一个因子会在循环的早些时候从n中提取出来。

由于这意味着循环可能以n为素数退出，因此有必要在循环之后插入一些代码来测试n是否大于1，如果大于1，则相应地调整totalFactor和primeFactor。

通过只测试素数作为候选因子，而不是测试从2开始的每个整数，该程序也可以更快。请注意，由于该程序需要支持高达2000000的数字，并且新循环将停止在n的平方根，因此只需要高达1414的素数。这种素数的列表可以很容易地提前准备好。