Finding prime numbers without exceeding time limits

Question

Okay first things first. Yes, this question is from a programming contest. No, I am not trying to cheat because the contest has ended 4 hours ago. I am pretty sure that my code is correct but the contest's compiler said that it is giving wrong answers. I tried an other compiler and it said "Time Limit Exceeded".

So, firstly, can you please tell me if the code is right or not? [One compiler said it wasn't]

If yes, then how can I make it more time efficient? [Another compiler said it was exceeding time limit]

---

PROBLEM A number is called a prime number if it is greater than 1 and has no divisors other than 1 and itself. The first few prime numbers are 2, 3, 5, 7, 11, 13,.. and so on. Given an integer X, find the smallest prime number which is not less than X

Input: The first line contains the number of test cases T. T cases follow. Each test case consists of an integer X in a separate line.

Output: Output T lines, one for each case containing the smallest prime number which is not less than X

Constraints: 1 <= T <= 10 1 <= X <= 1,000,000

Sample Input: 4 8 47 90 1130

Sample Output: 11 47 97 1151

Here is my solution:

int main() 
{
    int n;
    long int x, i, a;
    bool isPrime; // This flag will test if number is prime or not?
    cin>>n; // Here "n" will represent the number of test cases
    while(n)
    {
        cin>>x; // "x" is the number to be tested for the nth case

        if(x<=2)
        {
            cout<<2<<endl; // All numbers smaller than 3 will have the smallest prime number as 2.
            continue;
        }
        for(i=x;i<=1000000;i++) // Should I have checked values of "i" for odd numbers only? I forgot to try that... Would it have helped in reducing time complexity?
        {
            isPrime=true;
            for(a=2; a<i; a++) // Okay I tried making it (i/2)+1 but then the compiler said that it was a wrong answer. I am skeptical though...
            {
                if(i%a==0 and i!=2)
                    isPrime=false;
            }
            if(isPrime==true)
            {
                cout<<i<<endl;
                break;
            }
        }

        n--;
    }
    return 0;
}

Answer 1

To reduce confusion, make a function that checks whether a number is prime:

bool IsPrime(int x)
{
    isPrime=true;
    for(int a = 2; a < x; a++)
    {
        if (x % a == 0 && a != 2)
            return false;
    }
    return true;
}

Here, I didn't change your code, only restructured it. This is good, because this function is small, and any improvement to it is easy.

Remove edge case

There is no need to check a == 2, because you never call this function for 2. This makes inner loop smaller, providing better performance.

bool IsPrime(int x)
{
    isPrime=true;
    for(int a = 2; a < x; a++)
    {
        if (x % a == 0)
            return false;
    }
    return true;
}

Check fewer divisors

It is a well-known fact, and easy to check, that it's enough to check divisors up to sqrt(x). This gives much better performance!

bool IsPrime(int x)
{
    isPrime=true;
    for(int a = 2; a * a <= x; a++)
    {
        if (x % a == 0)
            return false;
    }
    return true;
}

At this point your program will probably be accepted by the time-checker. If you want better performance still, you can constrain divisors even further.

Check only prime divisors

Well, not really prime, but it's good to limit checking at least to odd numbers.

bool IsPrime(int x)
{
    isPrime=true;
    static const int a_few_primes[] = {2, 3, 5, 7, 11, 13};
    for (int a: a_few_primes)
    {
        if (x % a == 0)
            return false;
    }
    for(int a = 17; a * a <= x; a += 2)
    {
        if (x % a == 0)
            return false;
    }
    return true;
}

A note on the Sieve of Eratosthenes, which some other answerers recommend: it's good, but maybe you don't really need it, given that the number of test cases is very small (10).

Edit: removed some flawed analysis of performance.

The sieve method requires at least 1000000 iterations to build the list of prime numbers.

The trial method requires less than 500 iterations per number, trying less than 114 numbers until it finds a prime, and it does it 10 times, so the number of iterations is less than 500*114*10=570000.

Answer 2

I'm not going to solve it for you, but give you some hints.

1. Use the Sieve of Eratosthenes, which allows you to build up an array that you can afterwards use to know whether a number is prime in O(1).
2. Build the Sieve array once before you read any numbers, then you can read numbers and check each of them in constant time. Performing the same calculations for each number is overkill.