## sieve of EratosthenesThe most efficient way to find all of the smallest prime numbers. First described by Eratosthenes of Cyrene, it involves making a list of all the integers less than or equal to n (and greater than one), then striking out the multiples
of all primes less than or equal to the square root of n. The numbers
that are left are the primes. For example, to find all the primes less than
or equal to 30, we list the numbers from 2 to 30:
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30The first number, 2, is prime, so we keep it out and strike out all of its multiples, leaving 2 3 5 7 9 11 13 15 17 19 21 23 25 27 29The next number left, 3, is prime, so again we retain it and delete all of its multiples, leaving 2 3 5 7 11 13 17 19 23 25 29Now we do the same thing for 5, another prime, to give 2 3 5 7 11 13 17 19 23 29The next number, 7, is larger than the square root of 30, so all of the numbers left are primes. ## Related category• PRIME NUMBERS | |||||

Home • About • Copyright © The Worlds of David Darling • Encyclopedia of Alternative Energy • Contact |