时间戳

首页 > 解决方案 > 如何在快速运行时获得总的非素数？

c - 如何在快速运行时获得总的非素数？

问题描述

我在一个竞争激烈的编程网站上学习 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("%d\n", totalNPF(n));
    }

    return 0;
}

我使用数论概念，但它仍然很慢。它的运行时间超过 1 秒。有谁知道如何提高速度，以便我可以将速度提高到 1 秒或以下？

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

标签： c

解决方案

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

由于这意味着循环可能会n以主要因素退出，因此需要在循环后插入一些代码来测试是否n大于 1，如果是，则totalFactor进行primeFactor相应的调整。

通过仅测试素数作为候选因子而不是测试从 2 开始的每个整数，也可以使程序更快。请注意，由于程序需要支持最多 2,000,000 的数字，并且新循环将在 的平方根处停止，因此n只需要最多 1,414 个素数。这样的素数列表可以很容易地预先准备好。

推荐阅读