# Dolkar/Random-stuff

Switch branches/tags
Nothing to show
Fetching contributors…
Cannot retrieve contributors at this time
44 lines (31 sloc) 1.63 KB
 from itertools import takewhile, compress, islice few = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31] def getPrimes(n): """A pretty efficient way to compute all prime numbers up to n.""" if n < 37: # Let's grab it from the few primes listed above. return list(takewhile(lambda x: x <= n, few)) else: res = [True, False, True] * (n / 6 + 1) # Using this sequence and mapping only odd numbers, we can efficiently ignore # multiples of 2 and 3. start = int(n ** 0.5) - 1 # We will use only primes under this value for checking. start |= 1 # Ensures the number will be always even end = n / 2 # We ignore even numbers primes = getPrimes(start) # Getting the primes for checking recursively. for p in primes[2:]: # No need for 2 and 3 # Now, lets mark all multiples of the prime 'p' below 'n' as False. # Could be actually even more efficient using numpy. res[p * p / 2:end:p] = [False] * ((n - p * p - 1) / (p * 2) + 1) # Now, the primes we want are all the indices of 'True' values in res. # So let's convert them to numbers. Could actually return an iterator... # This part takes about one third of the overall computing time. the_part_we_use = islice(res, start / 2 + 1, end) return primes + list(compress(xrange(start + 2, n, 2), the_part_we_use)) if __name__ == '__main__': from timeit import Timer print getPrimes(200) i = 10 for x in xrange(7): print i, Timer("getPrimes(i)", "from __main__ import getPrimes, i").timeit(1) i *= 10