# How to find next prime number?

By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is 13. What is the 10001st prime number?

-
This is Project Euler problem 7: projecteuler.net/index.php?section=problems&id=7 – Douglas S. Stones Oct 29 '10 at 7:18
Yes! and I would like to know how to solve this. – Mayur Oct 29 '10 at 7:23
Just compute the first 10001 primes... – Hans Lundmark Oct 29 '10 at 7:56
You might want to look at the prime counting function. – J. M. Oct 29 '10 at 8:06

It is 104743, according to http://primes.utm.edu/lists/small/100000.txt and the related list of the first 10,000 primes ;-)

-
while true, this answer does not help in the spirit of Project Euler where this question originates from. OTOH, it is the answer, so +1. Mentioning the 10.000 list is a good hint indeed. – Tobias Kienzler Oct 29 '10 at 9:59

I assume you want to program this? Then the question belongs in a CS forum. However, I will try to motivate how to program this using properties of prime numbers:

1) For a number you could try to divide it by every single positive integer smaller than the respective number (except for 1). This is stupid, as you obviously could just search through the odd numbers (checking 2 first). But can you do even better?

2) Do you have to stop at n-1, or can you stop way earlier? You can. Find out where.

Now count primes.

-
I'd joke that the OP should try sieving, but s/he might take that seriously... – J. M. Oct 29 '10 at 10:11
@J. M.: Why is that a joke? For a small number like 10,001 this is probably the fastest approach. – Charles Oct 29 '10 at 23:55
I think he meant by hand. – M.B. Oct 30 '10 at 9:39
#include <stdio.h>
#include <string.h>

main()
{
int n,l,h,x,y,p,q;
printf("enter a number:");
scanf("%d",&n);
l=low(n);
h=high(n);
q=l-h;
x=n-l;
y=h-n;
p=x-y;

if(q==0)
printf("\n This is prime number:%d",n);
else if(p==0)
printf("\n The nearest prime numbers are:\n%d\n%d",l,h);
else if(x<y)
{
printf("\n The nearest prime number is:%d",l);
}
else
printf("\n\n The nearest prime number is:%d",h);

}

int high(int n)
{
int i,j,k;
for(i=n;i<=i+1;i++)
{
k=0;
for(j=1;j<=i;j++)
{
if(i%j==0)
{
k++;

}
}
if(k==2)
{
// printf("%d",i);
break;
}

}
return i;
}

int low(int n)
{
int i,j,k;
for(i=n;i>0;i--)
{
k=0;
for(j=1;j<=i;j++)
{
if(i%j==0)
{
k++;
}
}
if(k==2)
{
//printf("%d",i);
break;
}

}
return i;
}

-