Sphere Online Judge Issues (Prime Number Generator)

Question

Ok, so I enjoy using SPOJ to practice programming and developing algorithms. I always have issues with the questions though. A lot of times, I will get a "wrong answer" message when clearly my code answers the questions properly. If someone could tell me if there is anything wrong or why SPOJ would be telling me my answer was wrong that would be awesome! Here is the problem word-for-word:

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.

My code:

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;

INPUT:

2
7 11
2 9

OUTPUT:

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.

This is not one of those cases as evidenced by the fact that, despite the contrary, your code seems to think that 9 is a prime. The line:

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

combined with the fact that you appear to be printing all odd numbers (and two), is an indication that your prime check is incorrect.

---

Where you should probably start is with a simple prime check function such as:

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

Once you have it working, then worry about performance (two of my favourite mantras are "Wrong is the least optimised state" and "Get it working first, then get it working fast").

The things you can look into for optimisations include, but are not limited to:

• Eratosthenes sieve where, provided the range of primes isn't too large, it can greatly improve speed by not having to do a lot of calculations for each prime test; and
• Using the fact that all primes other than two and three are of the form 6n±1, effectively tripling the speed of the isPrime function (see here for an explanation).

For that second bullet point, you can use:

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