Problem Solutions: Problem 61 - Prime Numbers Generation

bpzzt_br 2014-11-09 16:13:32

I almost have the solution, but my code takes too long to generate 200000 primes! If it's 200 no problem, but more than that (2000, for example) the computer just sits there processing, processing...

I asked some enthusiasts in a Python community for help on Facebook and was able to improve the code a lot compared to the first versions (the first one didn't even work, logic was all wrong!), but still...

prime_list = [2]

list_limit = 0

while len(prime_list) < 200001:
    list_limit += 1
    for i in xrange(3, list_limit, 2):
        for j in prime_list:
            if i % j == 0:
                break
        else:
            prime_list.append(i)

nicolas_patrois 2014-11-09 16:27:33

A sieve from a well-known mathematician is faster.

Rodion (admin) 2014-11-09 16:37:25

Hi! Thanks for your question!

See, you are trying to generate 200000 primes, and for each of them you check divisibility by all of previously found primes! So you do 200000 iterations of the outer loop and in each of them 100000 iterations of inner loop. This means about 200000*100000 = 2e10 iterations!

With Python you should expect about million to ten millions iterations per second (1e6 to 1e7) which means that you'll need up to several hours with such approach. And it does not account for composite numbers which you skip and which also take some iterations!

But do you need to check divisibility by all preceding primes? No!

If you check probable divisors of value X and tried all primes up to P such that P*P > X (i.e. up to square root of X) then you need not proceed further. Can you guess why? :)

So you can significantly reduce amount of iterations in the inner loop (for j in prime_list) breaking out of it far earlier.

BTW please if possible, avoid publishing complete solutions in forum to save a bit of intrigue for your future colleagues :)

bpzzt_br 2014-11-10 02:36:30

Merci Nicolas, and thanks for the tips admin!

Sorry about posting the solution, I tried to edit now but the option is not available.

TestUser 2014-11-10 02:52:46

> Sorry about posting the solution, I tried to edit now but the option is not available.

Ah, no problem - this was not complete solution. :)

Hope the tips could be helpful. Feel free to ask more if they are not!

Really editing of messages is accessible only during first hour after posting...

UPD Excuse me for responding from test account - I was testing the last update and forgot to change back. I dared to shorten your code slightly so that the sense of the post is preserved, I hope.

Juan Arcila 2016-09-10 21:27:33

Hello, i can't understand why this is true!: If you check probable divisors of value X and tried all primes up to P such that P*P > X (i.e. up to square root of X) then you need not proceed further. Can you guess why? :) please help me

Quandray 2016-09-11 19:25:36

Hi Juan,

Try it with a few numbers, e.g. 206 & 303, and see what you are left with.