15.1 The Sieve of Eratosthenes and Factoring

   

 
Java Number Cruncher: The Java Programmer's Guide to Numerical Computing
By Ronald  Mak

Table of Contents
Chapter  15.   Prime Numbers


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:

graphics/15equ01.gif


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 

   
Top
 


Java Number Cruncher. The Java Programmer's Guide to Numerical Computing
Java Number Cruncher: The Java Programmers Guide to Numerical Computing
ISBN: 0130460419
EAN: 2147483647
Year: 2001
Pages: 141
Authors: Ronald Mak

flylib.com © 2008-2017.
If you may any questions please contact us: flylib@qtcs.net