领域在线判断问题(素数生成器)

Question

好的，所以我喜欢使用SPOJ来练习编程和开发算法。不过，我总是对这些问题有意见。很多时候，当我的代码正确地回答问题时，我会得到一个“错误的答案”信息。如果有人能告诉我，如果有什么问题，或为什么SPOJ会告诉我，我的答案是错误的，那将是可怕的！以下是逐字逐句的问题：

素数发生器 彼得想为他的密码系统生成一些素数。救救他！您的任务是在两个给定的数字之间生成所有素数！ 输入 输入以单行测试用例的t数(t<=10)开始。在下一个t行的每一行中，都有两个数字m和n (1 <= m <= n <= 1000000000, n-m<=100000)被空格分隔。 输出 对于每个测试用例，都要打印所有素数p，以便m <= p <= n，每一行一个数字，测试用例由一个空行分隔。

我的代码：

int n;
scanf("%d", &n);

if(n > 10){ return 0; }

n = n*2;
int arr[n];

for(int i = 0; i < n; i++){ scanf("%d", &arr[i]); }

for(int i = 0; i < n; i += 2){
    if(arr[i] >= 1 && arr[i] <= arr[i+1] && arr[i+1] <= 1000000000 && arr[i+1]-arr[i] <= 100000){
        for(int j = arr[i]; j <= arr[i+1]; j++){
            if(j % 2 == 1 || j == 2){
                printf("%d\n", j);
            }
        }
        printf("\n");
    }
}
return 0;

投入：

2
7 11
2 9

产出：

7
9
11

2
3
5
7
9

Answer 1

很多时候，当我的代码正确地回答问题时，我会得到一个“错误的答案”信息。

这不是其中的一种情况，尽管相反，您的代码似乎认为9是一个质数，这一点就证明了这一点。这句话：

if(j % 2 == 1 || j == 2)

再加上你似乎在打印所有的奇数(和两个)，这表明你的主要检查是不正确的。

您可能应该从一个简单的质数检查函数开始，例如：

int isPrime(int num) {
    int chk = 2;
    while (chk * chk <= num)
        if ((num % chk) == 0)
            return 0;
        ++chk;
    }
    return 1;
}

一旦你让它工作了，然后担心它的性能(我最喜欢的两个咒语是“错误是最不优化的状态”和“首先让它工作，然后让它快速工作”)。

您可以查看优化的内容包括，但不限于：

• Eratosthenes筛，如果素数的范围不太大，它可以大大提高速度，因为不需要为每一个质数测试做大量的计算；
• 使用的事实是，除2和3以外的所有素数都是6n±1形式的，有效地将isPrime函数的速度提高了两倍(请参阅here以获得解释)。

对于第二个要点，您可以使用：

int isPrime(unsigned int num) {
    // Special cases for 0-3.

    if (num < 2) return 0;
    if (num < 4) return 1;

    int chk = 5, add = 2;         // prime generator, 6n +/- 1.
    while (chk * chk <= num)      // check every candidate.
        if ((num % chk) == 0)     // check if composite.
            return 0;
        chk += add;               // next candidate.
        add = 6 - add;            // alternate +2, +4.
    }
    return 1;                     // no factors, must be prime.
}