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

Question

我必须打印 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 上提交此代码时出现“超出时间限制”错误。我怎样才能减少这个素数生成器的执行时间？

Answer 1

正如@Carcigenicate 所建议的那样，您已经超过了时间限制，因为您的主要发电机太慢了；而且它太慢了，因为您使用的是低效算法。

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

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