Question

calculating 100001st prime number question
i got the correct answer but takes forever to calculate . Can someone check code for me ?
Python BTW

number = 2
prime_count= int()


while prime_count < 10001:
cud_b_prime = True
divisor = 2
while divisor < number :
if number % divisor ==0:
cud_b_prime = False
divisor +=1

if cud_b_prime:
#print number
prime_count +=1
number +=1
print prime_count

Answer 1

A simple way of gaining efficiency is to skip the even numbers (2,4,6,8,10,...). We know that they are all prime and there is no reason to check them for primality. See the change below. I modified number so that it increments by +2 instead of +1. I made a couple of other slight adjustments (e.g. begin number at 5 and prime_count assigned at 2) in order to skip 2,3,4. These don't impact performance but was to get the counts come out correctly. In short, the quickest way to make it more efficient was to skip the even numbers.

number = 5
prime_count= 2


while prime_count < 1000:
cud_b_prime = True
divisor = 2
while divisor < number :
if number % divisor ==0:
cud_b_prime = False
divisor +=1

if cud_b_prime:
# print number
prime_count +=1
number +=2
print prime_count

Answer 2

Thanks malpaso
Tried ignoring even numbers and was a bit quicker but not much.
On Project Euler ppls code running in below 10 seconds . mine taking 10 mins :)

Answer 3

I think that your code takes that long because of the size of the input, the 100001 is a very large number. In order to reduce the time you'd need to change the algorithm in other words the mathematical way for calculating the n prime and make the order of growth logarithmic. (See Lec 08) Bad News is I don't know a logarithmic algorithm for this problem.

Answer 4

Mikeswell is correct. I thought you were trying to calculate the 1000th prime, not the 10000th prime. The standard algorithm is not efficient. On my Mac Air it took only a couple of minutes. I will look into finding some more efficient algorithms.

Answer 5

Current discussion on this subject here:

http://openstudy.com/study?F1244392739431MUOV2U=_#/updates/4f1241dbe4b0a4c24f583004

Answer 6

I wonder if you used the above code to get the answer. Print "prime_count " only prints the counter and not the nth prime number. Here's a little modification to your code http://pastebin.com/eWRWGkvZ
It will print the 1001th prime number. Takes a few seconds though. But as Mikeswell and Malpaso said, a more efficient code will be requrired to compute the 10001th prime number.

Answer 7

Hi
I took your original script and made a few changes:
1) The question only asks for odd numbers to be checked so increment the main loop by 2
2) I think we only need to check for divisors up to half of the could_be_prime because, if a number is divided by more than half of itself it must have a remainder:I am struggling to explain this, but try it on paper, and you'll see what I mean.
3) I couldn't work out how to do this starting with 1 so I set the initial could_be prime to 3 and set the prime_count to 2
4) Set script to find 1000th prime, instead of 10,000

number = 3
prime_count= 2

while prime_count < 1001:
cud_b_prime = True
divisor = 2
# Only need to check for divisors up to half of number
# because eg 9/5 must have a remainder and same for 11/6
while divisor < number/2 :
if number%divisor == 0:
cud_b_prime = False
#If we have found a divisor the number cannot be prime so
#exit the loop early by setting the divisor
#equal to the top limit ie number/2 - it will add 1
#at the bottom of the loop so it will certainly be
#bigger than number/2 by 1, so it will exit without
#trying the rest of the divisors
divisor = number/2
#otherwise keep increasing the divisor
divisor +=1
if cud_b_prime:
print prime_count,
print number
prime_count +=1
#The q. asks to check odd numbers only so increase by 2
number +=2
#Even if the loop has just gone thru for a non-prime this will
# print so move it back up to only print when we find a prime
#print prime_count

Seems to run OK
Cheers
Dave

Answer 8

@ntsdav561 you explained it very well! And the idea of setting divisor = number/2 is great and avoids unnecessary iterations after cud_be_prime is False. I just realized that setting the divisor upto the square root of the number makes it even faster and actually saves a lot of time if, let's say you wanna calculate the 10001th prime number. Cheers :)

Answer 9

Great idea about square root. That makes a huge impact on the number of calculations. I tried it with 2 changes to the code:
At the top of the script:
import math
And instead of :
while divisor < number/2 :
change to :
while divisor < int(math.sqrt(number))
That works fine