减少素数生成器的执行时间

debugcn 发表于 Dev

用户6927987

我必须打印两个限制n和m,之间的数字t。

我创建了t变量和两个指向整数值n, m保留内存块的指针t。

我使用指针而不是数组来执行更快的操作。

外for循环迭代每一个测试用例，增加m和n指针。

内for循环打印从m[i]到的素数n[i]。

代码

#include <stdio.h>
#include <stdlib.h>

int is_prime(int);

int main(void) {
    
    int t;
    int *n = malloc(sizeof(int) * t);
    int *m = malloc(sizeof(int) * t);

    scanf("%d", &t);
    for (int i = 0; i < t; i++, m++, n++) {
        scanf("%d %d", &m[i], &n[i]);
        for (int j = m[i]; j <= n[i]; j++) {
            if (is_prime(j)) {
                printf("%d\n", j);
            }
        }
        if (i < t - 1) printf("\n");
    }

    return 0;
}

int is_prime(int num)
{

    if (num <= 1) return 0;
    if (num % 2 == 0 && num > 2) return 0;
     
    for(int i = 3; i < num / 2; i+= 2){
         if (num % i == 0)
             return 0;
    }
    
    return 1;
}

问题：http : //www.spoj.com/problems/PRIME1/

代码在http://ideone.com上正确编译，但是当我尝试在 SPOJ 上提交此代码时出现“超出时间限制”错误。如何减少这个质数生成器的执行时间？

燕窝

正如@Carcigenicate 所暗示的那样，您超出了时间限制，因为您的主要生成器太慢了；而且它太慢了，因为您使用的是低效算法。

实际上，您不应该简单地测试每个连续数的素数（顺便说一句，您这样做也无效），而是应该使用已知素数（可能还有您计算的其他素数）一次排除多个值。例如，您不需要检查 5 和 10 的倍数（实际值 5 除外）的素性，因为您知道 5 将它们相除。因此，只需将各种素数的倍数“标记”为不相关即可。

...当然，这只是让您入门，您可以使用各种技巧进行优化 - 算法和实现相关。

本文收集自互联网，转载请注明来源。

如有侵权，请联系[email protected] 删除。