Archive for the ‘Primes’ Category
I just did this vid on Primes in Python, which is my top ranking popst here…
The Sieve of Eratosthenes is the most commonly known way to generate lists of primes. Those Greeks knew what they were doing ! It is a nice simple algorithm for beginning programmers. Start with all the natural numbers up to n, and then cross out all the composites starting with even numbers (greater than 2), then multiples of 3 and so on. once you have got up to crossing out multiples of the square root of n anything left must be prime.
As usual Python is straightforward:
There is some redundancy in this code because having started eliminating mutliples of two it then tries to eliminate multiples of 4 (of which there can’t be any since any multiple of 2 is also of 4 and will have been eliminated) and so on through 6,8,9 etc. Coding to avoid this seems to result in a slower and more cumbersome program so I kept it simple.
Notice that this is a generator, useful for finding more than one prime. It’s possibly the simplest to code but you should also look at exploring primes since the function there is faster as I timed it. For really large numbers even these tests can take much too long to be feasible, and that’s why specialists like cryptographers often rely on probabilistic tests that declare a number to be, say, 99.999% likely to be prime, although not 100% certain.
Another algorithm for generating all the primes up to a given number is called the “Sieve of Atkin”.
it is slightly more complex and we’ll leave it for later.
One of the first things a beginning programmer should try is code for testing the primality of a given number, or getting a list of primes. A prime is a number only divisible by itself and one. (Note that divisibility here means divisible without a remainder…)
Searching for big primes can get very subtle. This piece will only scratch the surface of primes, but it’s still a good challenge which sharpens our thinking. The code we will use will evolve through the article, so please read sequentially from the start.
There are two naive methods to find primes. First the Divisor Test which is useful for checking the primality of a given number, or small collection of numbers, second the Prime Sieve which is faster to generate lots of primes. Read the rest of this entry »