Printing the n'th prime numbers

Question

This is an online problem. The challenge is to print the k^th prime number, for each k given in the input (1 ≤ k ≤ 15000). The first line of input indicates the number of inputs on the subsequent N lines.

Example input:

4
1
2
3
4

Example output:

2
3
5
7

(the 1st 2nd 3rd and 4th prime numbers).

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define MAX 100000000

void prime(int n)
{
    int i,j,temp,count=0;

    for(i=2;i<=MAX;i++)
    {
        temp=0;
        for(j=2;j<=sqrt(i);j++)
        {
            if(i%j==0)
            {
                temp=1;
                break;
            }
        }
        if(temp==0)
        {
            count++;
        }
        if(count==n)
        {
            printf("%d\n",i);
            break;
        }
    }
}

int main()
{
   int n,i;

   scanf("%d",&n);
   int arr[n];

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

   return 0;
}

This code is working fine on codeblocks but is exceeding time limits on an online judge. I've tried manipulating this code in two more ways

1. using pointer and malloc in the main function
2. running the loop from j=1 to j=i/2 instead of upto sqrt(i)

(latter is more efficient due to fewer iterations of loop). Any suggestions?

Answer 1

Things that can be improved in the current algorithm

Before I start talking about other ways to find the primes, let's take a look at some of the things that could be improved in the current program.

1. I don't think temp is a very good name. I think you should change it to isPrime and then reverse the sense of it.
2. You only need to check count==n if the number was prime, not in all cases.
3. The break that you use when count==n actually causes the function to return. It would be more clear to just say return instead of break.
4. Instead of j<sqrt(i) as your loop condition, it would be better to just call sqrt(i) once before the loop instead of calling sqrt() once per loop. A smart compiler will optimize this for you, but you can't always depend on your compiler being that smart.
5. Instead of iterating through all integers, you can only iterate through all odd integers. This goes for both loops. The only even prime is 2 and you can check for that as a special case.

So after all the adjustments above, your code would look like this:

void prime(int n)
{
    int i,j,count=0;

    if (n == 1) {
        printf("2\n");
        return;
    }
    for(i=3;i<=MAX;i+=2)
    {
        int isPrime=1;
        int jMax = sqrt(i);
        for(j=3;j<=jMax;j+=2)
        {
            if(i%j==0)
            {
                isPrime=0;
                break;
            }
        }
        if(isPrime)
        {
            if(++count==n)
            {
                printf("%d\n",i);
                return;
            }
        }
    }
}

This code runs 2x faster than the original function. But that's still not fast enough.

Wasting computation

The way you are currently going about the problem is that you find each prime independently of the next. So if you are asked to find the 150000th prime followed by the 149999th prime, you will spend a whole lot of time finding the 150000th prime and then throw away all your work and spend a whole lot of time finding the 149999th prime, even though you already found that prime the first time around!

You could do a lot better by:

1. Figuring out the biggest prime that you are asked for.
2. Find all the primes up to that prime in one call to prime().
3. Now that you have all the primes, print out the ones you were asked to find one by one.

This reduces the problem by a factor of N, where N is the number of primes you were asked to find. Let's see what this new program would look like:

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define MAX 100000000

void prime(int n, int *primes)
{
    int i,j,count=0;

    primes[count++] = 2;
    if (count == n)
        return;
    for(i=3;i<=MAX;i+=2)
    {
        int isPrime=1;
        int jMax = sqrt(i);
        for(j=3;j<=jMax;j+=2)
        {
            if(i%j==0)
            {
                isPrime=0;
                break;
            }
        }
        if(isPrime)
        {
            primes[count++] = i;
            if(count==n)
                return;
        }
    }
}

int main()
{
   int n,i;

   scanf("%d",&n);
   int arr[n];
   int maxPrime = 0;

   for(i=0;i<n;i++)
   {
       scanf("%d",&arr[i]);
       if (arr[i] > maxPrime)
           maxPrime = arr[i];
   }
   int primes[maxPrime];
   prime(maxPrime, primes);
   for (i=0;i<n;i++)
   {
       printf("%d\n", primes[arr[i]-1]);
   }
   return 0;
}

Other ways

Of course there are other ways to do this even faster. For example, you can use the "Sieve of Eratosthenes" method. But for the purposes of your online problem, I'm sure that the key factor was to use a one pass solution instead of an N pass solution. That was the stumbling block in your current solution.

Answer 2

You are trying to iterate over all numbers and check if each is prime which you do in O(n sqrt n) time. This might be feasible if you switch to a more efficient primality check, such as the Miller-Rabin primality test, as it is deterministic within certain limits depending on the probes.

A simpler way to do this is to generate primes until you are done. This can easily be done by the Sieve of Eratosthenes in roughly O(n log log n) time.

You can run the sieve once, get all the primes up to 175000 (15000th prime is 163841 according to a bit of googling) and then answer all the queries in constant time by dumping all the primes into an ArrayList (in order of course).

If those methods aren't fast enough, look into even faster sieving algorithms such as Sieve of Sundaram and Sieve of Atkin.