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

Question

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

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

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

外部 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 可以整除它们。所以只是 "mark" 各种素数的倍数是无关紧要的。

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

Answer 2

我知道您正在寻找算法改进，但以下技术优化可能会有所帮助：

如果你使用Visual Studio，你可以使用alloca而不是malloc，这样n和m进入栈而不是堆。

您也可以尝试使用数组而不是指针重写您的算法，将 n 和 m 放入堆栈。

如果您想继续使用指针，请在星号后使用 __restrict 关键字，这会提醒编译器您没有引用这两个指针。

Answer 3

有几种方法可以改进整数的素性检查 n。以下是一些您可能会觉得有用的内容。

减少检查次数：一个众所周知的定理给出了一个事实，如果你想寻找 n 的因数，让比如 n = a * b，那么你可以在 1 和 sqrt(n) 之间寻找一个除数。（证明很简单，主要论证是我们有三种情况，或者 a = b = sqrt(n)，或者我们有 a < sqrt(n) < b 或 b < sqrt(n) < a。而且，无论我们属于哪种情况，都会有一个1 和 sqrt(n) 之间 n 的因数）。
使用埃拉托色尼筛法：这种方法允许丢弃以前不合格的不必要的候选人（参见Sieve of Eratosthenes（维基百科））
使用概率算法：如今检查素数最有效的方法是使用概率测试。实现起来有点复杂，但效率更高。您可以找到其中一些技术 here (Wikipedia)。

Answer 4

你甚至可以在不使用指针或数组的情况下做到这一点

#include <stdio.h>
#include<math.h>

int is_prime(long n){
    if (n == 1 || n % 2 == 0)
        return 0;
    if (n == 2)
        return 1;
    for (long i = 3; i <= sqrt(n); i += 2) {
        if(n % i == 0)
            return 0;
    }
    return 1;
}
int main() {
    int t;
    scanf("%d",&t);
    while(t--) {
        long n, m;
        scanf("%ld %ld",&n,&m);

        for (long i = n; i <= m; i++) {
            if (is_prime(i) == 1)
            printf("%ld\n",i);
        }
    }
    return 0;
}

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

Reduce execution time of prime number generator

c

algorithm

primes

代码