The Sieve of Eratosthenes [1] is a simple way to determine, among the integers 2 through n, which are prime and which are composite. We begin with the integers, 1 through 100, say, arranged in a table: [1] Eratosthenes (276 C194 B.C. ) was a Greek mathematician and philosopher who studied prime numbers and who is also known for accurately computing the earth's circumference. 1 | 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 | 30 | 31 | 32 | 33 | 34 | 35 | 36 | 37 | 38 | 39 | 40 | 41 | 42 | 43 | 44 | 45 | 46 | 47 | 48 | 49 | 50 | 51 | 52 | 53 | 54 | 55 | 56 | 57 | 58 | 59 | 60 | 61 | 62 | 63 | 64 | 65 | 66 | 67 | 68 | 69 | 70 | 71 | 72 | 73 | 74 | 75 | 76 | 77 | 78 | 79 | 80 | 81 | 82 | 83 | 84 | 85 | 86 | 87 | 88 | 89 | 90 | 91 | 92 | 93 | 94 | 95 | 96 | 97 | 98 | 99 | 100 | First, we remove the number 1, which is neither prime nor composite. The next number, 2, is the first prime. We leave it alone but remove each subsequent multiple of 2 all even numbers greater than 2 are composite, since they are all divisible by 2. 1 | 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 | 30 | 31 | 32 | 33 | 34 | 35 | 36 | 37 | 38 | 39 | 40 | 41 | 42 | 43 | 44 | 45 | 46 | 47 | 48 | 49 | 50 | 51 | 52 | 53 | 54 | 55 | 56 | 57 | 58 | 59 | 60 | 61 | 62 | 63 | 64 | 65 | 66 | 67 | 68 | 69 | 70 | 71 | 72 | 73 | 74 | 75 | 76 | 77 | 78 | 79 | 80 | 81 | 82 | 83 | 84 | 85 | 86 | 87 | 88 | 89 | 90 | 91 | 92 | 93 | 94 | 95 | 96 | 97 | 98 | 99 | 100 | After 2, the next prime is 3, and so we leave 3 alone but remove all of its subsequent multiples . (Many of the numbers will have already been removed.) 1 | 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 | 30 | 31 | 32 | 33 | 34 | 35 | 36 | 37 | 38 | 39 | 40 | 41 | 42 | 43 | 44 | 45 | 46 | 47 | 48 | 49 | 50 | 51 | 52 | 53 | 54 | 55 | 56 | 57 | 58 | 59 | 60 | 61 | 62 | 63 | 64 | 65 | 66 | 67 | 68 | 69 | 70 | 71 | 72 | 73 | 74 | 75 | 76 | 77 | 78 | 79 | 80 | 81 | 82 | 83 | 84 | 85 | 86 | 87 | 88 | 89 | 90 | 91 | 92 | 93 | 94 | 95 | 96 | 97 | 98 | 99 | 100 | We continue similarly with the prime numbers 5, 7, 11, and so on until we've "sieved out" all the primes: 1 | 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 | 30 | 31 | 32 | 33 | 34 | 35 | 36 | 37 | 38 | 39 | 40 | 41 | 42 | 43 | 44 | 45 | 46 | 47 | 48 | 49 | 50 | 51 | 52 | 53 | 54 | 55 | 56 | 57 | 58 | 59 | 60 | 61 | 62 | 63 | 64 | 65 | 66 | 67 | 68 | 69 | 70 | 71 | 72 | 73 | 74 | 75 | 76 | 77 | 78 | 79 | 80 | 81 | 82 | 83 | 84 | 85 | 86 | 87 | 88 | 89 | 90 | 91 | 92 | 93 | 94 | 95 | 96 | 97 | 98 | 99 | 100 | Once we have a table of prime numbers, we can use it to compute the prime factors of a composite number by repeatedly dividing the composite number by the prime numbers that evenly divide it, until the composite number is reduced to 1. For example, take the composite number 84: and so the prime factors of 84 are 2, 3, and 7, and 84 = 2 2 x 3 x 7. Listing 15-0a shows class PrimeFactors in package numbercruncher.mathutils along with some test output. Listing 15-0a The Sieve of Eratosthenes and prime factors. package numbercruncher.mathutils; import java.util.Vector; import java.util.Enumeration; /** * Compute the Sieve of Eratosthenes and prime factors. */ public class PrimeFactors { /** * Compute the Sieve of Eratosthenes. * @param n the size of the sieve * @return the sieve as a boolean array (each element is true * if the corresponding number is prime, false if the * number is composite) */ public static boolean[] primeSieve(int n) { int halfN = (n+1) >> 1; boolean sieve[] = new boolean[n+1]; // Initialize every integer from 2 onwards to prime. for (int i = 2; i <= n; ++i) sieve[i] = true; int prime = 2; // first prime number // Loop to create the sieve. while (prime < halfN) { // Mark as composites multiples of the prime. for (int composite = prime << 1; composite <= n; composite += prime) sieve[composite] = false; // Skip over composites to the next prime. while ((++prime < halfN) && (!sieve[prime])); } return sieve; } /** * Compute the prime factors of an integer value. * @param n the value to factor * @return an array of distinct prime factors */ public static int[] factorsOf(int n) { boolean isPrime[] = primeSieve(n); // primes <= n Vector v = new Vector(); // Loop to try prime divisors. for (int factor = 2; n > 1; ++factor) { if (isPrime[factor] && (n%factor == 0)) { // Prime divisor found. v.add(new Integer(factor)); // Factor out multiples of the divisor. do { n /= factor; } while (n%factor == 0); } } // Create an array of the distinct prime factors. int factors[] = new int[v.size()]; Enumeration e = v.elements(); for (int i = 0; e.hasMoreElements(); ++i) { factors[i] = ((Integer) e.nextElement()).intValue(); } return factors; } /** * Main for testing. * @param args the commandline arguments (ignored) */ public static void main(String args[]) { AlignRight ar = new AlignRight(); // Test Sieve of Eratosthenes. System.out.println("The Sieve of Eratosthenes:\n"); boolean isPrime[] = primeSieve(100); for (int i = 1; i <= 100; ++i) { if (isPrime[i]) ar.print(i, 4); else ar.print(".", 4); if (i%10 == 0) ar.println(); } System.out.println(); // Test prime factors. int k[] = {84, 1409, 3141135, }; for (int i = 0; i < k.length; ++i) { int factors[] = factorsOf(k[i]); System.out.print("The prime factors of " + k[i] + " are"); for (int j = 0; j < factors.length; ++j) { System.out.print(" " + factors[j]); } System.out.println(); } } } Output: The Sieve of Eratosthenes: . 2 3 . 5 . 7 . . . 11 . 13 . . . 17 . 19 . . . 23 . . . . . 29 . 31 . . . . . 37 . . . 41 . 43 . . . 47 . . . . . 53 . . . . . 59 . 61 . . . . . 67 . . . 71 . 73 . . . . . 79 . . . 83 . . . . . 89 . . . . . . . 97 . . . The prime factors of 84 are 2 3 7 The prime factors of 1409 are 1409 The prime factors of 3141135 are 3 5 29 83 |