Question

I tried problem set 1. The question was
Write a program that computes and prints the 1000th prime number.

I went ahead to calculate 41538th prime number, which is 499979.
At first I tried a method which dividing in range
range(3, int(math.sqrt(i))+2,2)
#see program for more info

but later I realized that instead of dividing with odd numbers, I should divide with prime numbers before that number's square root. For this purpose I used a mutable list, at the end of which each calculated prime number is added.

Answer 1

Both seem to be calculating the prime numbers correctly, but when I remove all print statements (except the last) trying to just get the final answer, the division by prime number approach (method 2) doesn't seem to work. Does this have anything to do with efficiency of lists opposed to tuples?

Program is attached here, it shows which steps correspond to which method, comment out one set and uncomment the other.

Answer 2

Now I remember that range returns a list and not tuple. Now I'm even more confused.

Answer 3

You've kind of gotten off on a tangent. A while back, we argued this problem to get the fastest solution. for loops, IMO, aren't the best loop to use for this. A while loop is better.

primeList = [ 2, 3 ]
number = 5
while( len( primeList ) < 1000 ):
# figure primacy ( you've had a couple of real good insights on this )
number += 2

print primeList[ -1 ]

Answer 4

To add to rsmith's reply: I've tried your program, and both methods work fine, but method 2 is much MUCH slower. That's because for method 1, you put an upper bound to your list (the one generated by range), which is the square root of i. Whereas with method 2, you iterate over your *whole* list of primes everytime... ;)

Answer 5

Wait, that may be confusing, you have two lists generated by range. I meant the one in the for loop, not the odd_numbers one.

Answer 6

```
for j in range(3, int(math.sqrt(i))+2,2): #method 1
if i%j == 0:
prime_found = False
break
prime_found = True
```
This will always end in `prime_found = True`. Even when you realize a number is composite, you immediately set it to true.

Answer 7

Here's an implementation of a sieve i've used on a few projecteuler.net problems sieves are really the best way to identify primes.

def makeprimelist(bound):
max_ndx = (bound - 1) / 2
sieve = [True] * (max_ndx + 1)
for ndx in range(int(bound ** 0.5) / 2):
if sieve[ndx]:
num = ndx * 2 + 3
sieve[ndx+num:max_ndx:num] = [False] * ((max_ndx-ndx-num-1)//num + 1)
return [2] + [ndx * 2 + 3 for ndx in range(max_ndx) if sieve[ndx]]

Answer 8

http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes is a great explanation of the logic, but you're pretty much there already

Answer 9

Honestly the animated pic in the corner of the wikipedia page is what made the logic click for me all those years ago

Answer 10

@rsmith6559 : I'll check the program using while loops to see if time improves.

@kizolk: Thanks, now I realize that prime list grows much faster compared to square root.
I printed
```
print prime_list[-1],len(prime_list)
print current_prime, len(range(3, int(math.sqrt(i))+2,2))
```
and was amazed by difference in list size.
sqrt(499979)/2 = ~353
whereas for 41538th prime, the len(prime_list) should be 41538 and that is seriously a huge difference.

@wio: I think it still will work. The reason is that prime_found = True is part of the for loop which will continue until either it breaks if i%j == 0 or the counter finishes. When counter finishes, prime_found = True, and will be checked in next if block to see if the loop was broken or it finished. I could probably declare j before hand and calculate sqrt(i), and try checking its value after loop to see if loop finished or broke, but I think this method isn't much different in efficiency either.

Answer 11

@seandisanti Oh, thanks for reply. I'll look at these too.