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.
- 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.
- You only need to check
count==n
if the number was prime, not in all cases.
- 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
.
- 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.
- 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:
- Figuring out the biggest prime that you are asked for.
- Find all the primes up to that prime in one call to
prime()
.
- 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.