c - Sphere 在线判断问题(质数生成器)

Question

好的，所以我喜欢使用 SPOJ 来练习编程和开发算法。不过，我总是对这些问题有疑问。很多时候，当我的代码清楚地正确回答问题时，我会收到“错误答案”消息。如果有人能告诉我是否有任何问题或为什么 SPOJ 会告诉我我的回答是错误的，那就太棒了!这是逐字逐句的问题:

Prime Number Generator

Peter wants to generate some prime numbers for his cryptosystem. Help him! Your task is to generate all prime numbers between two given numbers!

Input

The input begins with the number t of test cases in a single line (t<=10). In each of the next t lines there are two numbers m and n (1 <= m <= n <= 1000000000, n-m<=100000) separated by a space.

Output

For every test case print all prime numbers p such that m <= p <= n, one number per line, test cases separated by an empty line.

我的代码:

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

A lot of times, I will get a "wrong answer" message when clearly my code answers the questions properly.

这不是这些情况之一，事实证明，尽管相反，您的代码似乎认为 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;
}

一旦你让它工作，然后担心性能(我最喜欢的两个口头禅是“错误的是最少优化状态”和“首先让它工作，< em>然后让它快速工作”)。

您可以考虑进行优化的事项包括但不限于:

• 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.
}