maybe i'll type stuff here…

Posts tagged ‘Programming’

Prime numbers using Python

I recently saw a post over at Stack Overflow on calculating prime numbers. In one of the responses the poster posted a C# example using the Sieve of Eratosthenes on a single line of code and although this is not ideal and extremely hard to read/figure out, I really wanted to see if I could do this in python. This is what I came up with:

reduce(lambda r, i: filter(lambda m: not (m > r[i] and m % r[i] == 0), r), \ 
	[range(2, 1000000)] + range(n + 1))[:n]


This is virtually an exact copy of the example at SO.

The 1,000,000 limit is overkill (and slow) if you only want to get the first 10 primes or so, since it only calculates the first num primes but runs through the whole list of 1,000,000 initial numbers (Getting the first 10 primes resulted in a list with 152,850 values of which only the first 10 are guaranteed to be prime).

Silly primes

Since there is no constant rate of change between primes, it is difficult to determine what the limit must be based on num. The limit is really a value greater than the num‘th prime.  A simple solution would be to multiply num by 10 and using that as the limit. This follows the assumption that there will be at least one prime every 10 numbers, i.e. there will be at least 1 prime between 1 and 10 and there will be at least 10 primes between 1 and 100. This is by no means foolproof, and only works up to prime 6,453 (64,499).

If you want to go bigger, check if num is greater than 6,453 and if it is, multiply it by 20 instead. This should then work up to prime 69,709,734 (1,394,194,679) but you might not reach it because it takes quite a significant amount of time and memory to get there. In fact it failed on my machine due to memory issues. The only way I could determine the last prime this could calculate was to multiply several num‘s by 20 and checking when the prime at num position exceeds the result and subtract 1;

limit is 69,709,735 * 20 = 1,394,194,700
prime at position 69,709,735 = 1,394,194,723 <- prime is higher than limit

limit is 69,709,734 * 20 = 1,394,194,680
prime at position 69,709,734 = 1,394,194,679 <- prime is lower than limit