1

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 10 001st prime number?

I have tried like this:

def isprime(num):
    i=2
    import math
    while (int(math.sqrt(num))+1)>=i:
        if num%i==0:
            return False
        i = i+1
    return True



def findprime(n):
    prime = 1
    for i in range(3,n):
        if isprime(i):
            prime = prime+1
        if prime ==  10001:
            return i

I am calling the findprime() with a big integer. so Its loop through all the integer within the range and its take a lot of time to generate the output and sometime my python shell hanged because of the large input. Is there any smart way to do this?

BenMorel
  • 34,448
  • 50
  • 182
  • 322
Kousik
  • 21,485
  • 7
  • 36
  • 59
  • 5
    http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes ? –  Nov 15 '13 at 13:06
  • 2
    These questions are duplicates inasfar as that question answers your question. – George Stocker Nov 15 '13 at 13:08
  • 2
    Hey, when you solve problem on ProjectEuler, you can click on icon with a guy in blue shirt and look, how other people solved this problem. There are usually very good answers. It's not response for your question, but an advice ;) – marxin Nov 15 '13 at 13:09
  • 1
    One small optimisation to your algorithm : prime numbers usually have the form of multiples of 6 plus or minus 1. So you can reduce your prime number testing to a third of the values you are testing, starting with 5. – Alex Barac Nov 15 '13 at 13:10
  • @bzykubd i think in ProjectEuler you can only see the answer after giving the right answer. thats why I am not able to see those answer which one i am not able to solve. – Kousik Nov 15 '13 at 13:23
  • "so Its loop through *all* the integer within the range" - not true. – Karoly Horvath Jun 18 '14 at 09:48

0 Answers0