calculate the 10001st prime number

[topologh]

I'm learning python by following project euler. Q7 asks you to calculate the 10001st prime.

i did the following (in pseudocode):

def div(n): makes a list of all the divisors.
def prim(n): checks if n is prime by check the list of all divisors. If len(div(n)) == 2, 2 is prime.

then i asked the computer to find all primes from 1 to 100000 with the above functions:


------------------------------------

y = []  
m = 1 
while m < 100000:
  if prim(m) == True: y = y + [m]
  m = m + 1

------------------------------------

but of course, it was taking too long.

Is there an easier way of doing this?

What i'm doing now is: I'm calculating how many primes are there between 0k and 10k, then 10k to 20k, then 20k to 30k.... summing the quantities, and when it gets to 10001, i print the primes and look for it. but this is a terrible solution....

[Zatox11]

I am not 100% sure if that is exactly what you want, but here:

def calcPrim(number):
    primList = []
    primList.append(2)
    value = 3
    while len(primList) < number:
        if checkPrim(primList, value):
            primList.append(value)
        value += 1
    primList.insert(0, 1)
    return primList

def checkPrim(primList, value):
    for prim in primList:
        if value%prim == 0:
            return False
    return True

number = 10001
primList = calcPrim(number)
print('{}th prime = {}'.format(number,primList[number-1]))

[ljmetzger]

Two clues for speeding up the algorithm:
a. You can increment by 2 each time, since we know that even numbers can't be prime.
b. the algorithm does not have to increment up to the number, since we also know that the largest prime can't be more than the square root of the number.

Lewis

[Zatox11]

thanks, these two improvements actually make a lot of difference in performance.
improved code:

def calcPrim(number):
    primList = []
    primList.append(2)
    value = 3
    while len(primList) < number:
        if checkPrim(primList, value):
            primList.append(value)
        value += 2
    primList.insert(0, 1)
    return primList

def checkPrim(primList, value):
    for prim in primList:
        if prim>sqrt(primList[-1]+2): break
        if value%prim == 0: return False
    return True

number = 10001
primList = calcPrim(number)
print('{}th prime = {}'.format(number,primList[number-1]))

old code: 5.741328477859497s to calculate
new code: 0.273015499114023s to calculate

[redmartian]

I've been trying to understand line 14
I really don't get it

[jefsummers]

primList[-1] refers to the last item in primList. Cool, you don't need to know how long primList is. So, if prim> square root of the last identified prime + 2, then break. Break takes you out of the innermost loop, in this case the for loop in line 13.

[redmartian]

I tried your exact code
It gave me a wrong result
I changed that line that was confusing me to check if the current prime number is greater than the value's square root
And it worked perfectly

 def prime(number):
    primes = []
    primes.append(2)
    value = 3
    
    while len(primes) < number:
        
        if check(primes, value):
            primes.append(value)
        value += 2
        
    return primes[number+1]
    
def check(primes, value):
    for prime in primes:
        if prime > math.sqrt(value): 
            break
        if value % prime == 0: 
            return False
            
    return True

number = 10001
primes = prime(number)
print('{}th prime = {}'.format(number,primes[number]))

[deanhystad]

The code is testing if the new number is divisible by any of the primes. Any non-prime number can be represented as a product of prime numbers. When testing if 69 is prime there is no reason to check if 71 is divisible by 9 (which is 3 * 3) or 15 (3 * 5) or 21 (3 * 7). There is also no need to test if 71 is divisible by 11. 71 was divisible by 11, it would also be divisible by 6 or 7. There is no reason to test factors that are greater than the square root of the number. If you put the two of these together you have a pretty efficient test. You can skip all non-primes and any number greater than the square root of the potential prime. To determine if 3 is prime, the program doesn't have to test any factors at all because we know the factor has to be less than 2, and there are no primes less than 2. When testing for 13 we only have to test 2 and 3 because 5, the next prime, is greater than the square root of 13.

A few quibbles. The first two prime numbers are [2, 3] not [0, 1]. You waste a lot of time calculating square roots. For each possible prime you should only calculate the square root once. Just imagine how fast your code would be if you removed 26,181 square root calculations. I would not write this using a helper function. A generic function that determines if a number is prime is useful to have, but this is a very specialized test that can only be used with the known prime list. It is easy to combine the two.

def primes(count):
    known_primes = [2]
    value = 3
    while count > 1:
        root = int(value**0.5)
        for p in known_primes:
            if p > root:
                count -= 1
                known_primes.append(value)
                break
            elif value % p == 0:
                break
        value += 2
    return known_primes

count = int(input('Enter number of primes '))
print(f'Prime[{count}] = {primes(count)[-1]}')