Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
3  
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
8  
Just compute the first 10001 primes... –  Hans Lundmark Oct 29 '10 at 7:56
1  
You might want to look at the prime counting function. –  J. M. Oct 29 '10 at 8:06
add comment

3 Answers 3

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

share|improve this answer
    
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
add comment

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.

share|improve this answer
1  
I'd joke that the OP should try sieving, but s/he might take that seriously... –  J. M. Oct 29 '10 at 10:11
1  
@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
1  
I think he meant by hand. –  M.B. Oct 30 '10 at 9:39
add comment
#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;
}
share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.