Amber Roxanna Amber Roxanna - 2 months ago 10
Python Question

How to generate the 1000th prime in python?

count = 0
i = 11

while count <= 1000 and i <= 10000:
if i%2 != 0:
if (i%3 == 0 or i%4 == 0 or i%5 == 0 or i%6 == 0 or i%7 == 0 or i%9 == 0):
continue
else:
print i,'is prime.'
count += 1
i+=1


I'm trying to generate the 1000th prime number only through the use of loops. I generate the primes correctly but the last prime i get is not the 1000th prime. How can i modify my code to do so. Thank in advance for the help.

EDIT: I understand how to do this problem now. But can someone please explain why the following code does not work ? This is the code I wrote before I posted the second one on here.

count = 1
i = 3
while count != 1000:
if i%2 != 0:
for k in range(2,i):
if i%k == 0:
print(i)
count += 1
break
i += 1

Answer

Let's see.

count = 1
i = 3
while count != 1000:
    if i%2 != 0:
       for k in range(2,i):
          if i%k == 0:        # 'i' is _not_ a prime!
            print(i)       # ??
            count += 1     # ??
            break
     i += 1          # should be one space to the left,
                     # for proper indentation

If i%k==0, then i is not a prime. If we detect that it's not a prime, we should (a) not print it out, (b) not increment the counter of found primes and (c) we indeed should break out from the for loop - no need to test any more numbers.

Also, instead of testing i%2, we can just increment by 2, starting from 3 - they will all be odd then, by construction.

So, we now have

count = 1
i = 3
while count != 1000:
    for k in range(2,i):
        if i%k == 0:       
            break
    else:
        print(i)
        count += 1
    i += 2        

The else after for gets executed if the for loop was not broken out of prematurely.

It works, but it works too hard, so is much slower than necessary. It tests a number by all the numbers below it, but it's enough to test it just up to its square root. Why? Because if a number n == p*q, with p and q between 1 and n, then at least one of p or q will be not greater than the square root of n: if they both were greater, their product would be greater than n.

So the improved code is:

from math import sqrt

count = 1
i = 1
while count < 1000:
    i += 2
    for k in range(2, 1+int(sqrt(i+1))):
        if i%k == 0:       
            break
    else:
        # print(i) ,
        count += 1
        # if count%20==0: print ""
print i

Just try running it with range(2,i) (as in the previous code), and see how slow it gets. For 1000 primes it takes 1.16 secs, and for 2000 – 4.89 secs (3000 – 12.15 ses). But with the sqrt it takes just 0.21 secs to produce 3000 primes, 0.84 secs for 10,000 and 2.44 secs for 20,000 (orders of growth of ~ n2.1...2.2 vs. ~ n1.5).

The algorithm used above is known as trial division. There's one more improvement needed to make it an optimal trial division, i.e. testing by primes only. An example can be seen here, which runs about 3x faster, and at better empirical complexity of ~ n1.3.


Then there's the sieve of Eratosthenes, which is quite faster (for 20,000 primes, 12x faster than "improved code" above, and much faster yet after that: its empirical order of growth is ~ n1.1, for producing n primes, measured up to n = 1,000,000 primes):

from math import log

count = 1 ; i = 1 ; D = {}
n = 100000                        # 20k:0.20s 
m = int(n*(log(n)+log(log(n))))   # 100k:1.15s 200k:2.36s-7.8M 
while count < n:                  #            400k:5.26s-8.7M 
        i += 2                    #            800k:11.21-7.8M 
        if i not in D:            #            1mln:13.20-7.8M (n^1.1)
            count += 1
            k = i*i
            if k > m:  break      # break, when all is already marked
            while k <= m:
                D[k] = 0 
                k += 2*i
while count < n:
        i += 2
        if i not in D: count += 1
if i >= m: print "invalid: top value estimate too small",i,m ; error
print i,m  

The truly unbounded, incremental, "sliding" sieve of Eratosthenes is about 1.5x faster yet, in this range as tested here.