Hi, i've started on some Project Euler problems so I can get to learn python -- I might have a few questions about different things!
I had a question about generating prime numbers - a few of the problems so far have been about primes, so having a nice fast script would be quite useful.
I made v1, which seemed to be ok... until I needed the 10001st prime - then it took about 20 mins to crunch through to a (correct) answer
I have now coded v2, which gets to 10001st in <2 secs.
v1: Takes a 'candidate prime', checks if it is prime by checking (candidate % div == 0) against the current list of confirmed primes, primes = [2, 3, 5, 7...etc etc]". If the candidate is prime, append to primes; if not, take the next odd number as the new candidate (until some specified limit).
Problem: it was very slow! I guessed that, in order to loop through all the confirmed primes, when I call my isItAPrimeNumber(candidate) function, Python has to hold the *entire* list of confirmed primes in memory, in order to test each one... Is this correct? Using python -m profiler, it tells me all the processing time is going to this function, but not really anything more detailed.
v2: Takes the 'candidate' and simply divides by 2, 3, 5, 7, 9... etc (basically just odd numbers) until it either a) finds a divisor; or b) gets too big (sqrt of the candidate). Now, we don't hold anything in memory -- just the integer that is being used as a divisor, which is incremented by 2 at the end of each loop.
Questions: It feels like v2 is "logically inefficient" -- I shouldn't be testing 9 (= 3*3), 15 (3*5), 21 (3*7) at all, since I have already tested 3, 5 and 7...... but it must be more "computationally efficient" to simply test all the odd numbers, because the computer is faster at doing the 'stupid thing' (incrementing the divisor) than the 'smart thing' (load primes into memory, grab each item and use as divisors). With low numbers it probably doesn't make much difference - a lot of the odd numbers will be prime anyway. But as the range increases, we are pointlessly testing a lot of odd numbers which have prime factors themselves (altough this seems to be massively compensated for, by not having to load the massive list of primes into memory anyways).
Is there a 'smart way' to grab items from primes one at a time?? Or is that just part of the game, because of the way Python deals with list objects?
(I've been reading a bit about 'generators' but I don't really understand. It feels like this should be part of the solution, but I could be wrong. Also - i am learning python! And never really done any OOP before either!)
Thanks for reading! Hope that was relatively clear...