Amber Roxanna - 8 months ago 37

Python Question

`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`

.

```
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 `~ n`

vs. ^{2.1...2.2}`~ n`

).^{1.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 `~ n`

. ^{1.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 `~ n`

, for producing ^{1.1}`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.