Sieve of Eratosthenes Prime Number :-
Seive of Eratosthenes find the number on the based of upper bound, where you say, find the prime number less than equal to n.
Seive of Eratosthenes mark all the composite number first and then find all the non-composite number as prime number.
We know that 2 is the first prime number, so all the multiple of 2 would be composite number, Seive of Eratosthenes will mark all such number as composite and he will take next prime from the list and all it's multiple would be marked as composite number. This process will be followed till square root of n.
So Seive of Eratosthenes algorithm will be like below:-
- For all numbers m: 2 .. √n, if m is unmarked:
- add m to primes list;
- mark all it's multiples, starting from square, lesser or equal than n (k * m ≤ n, k ≥ m);
- otherwise, if m is marked, then it is a composite number;
- check all numbers in range √n .. n. All found unmarked numbers are primes, add them to list.
2 is prime number so we will mark all multiple of 2 starting from square of 2 means 4 as composite number as in below table.
|
|
|
3
|
|
5
|
|
7
|
|
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
|
3 is the next prime number so we will make all multiple of 3 starting from square of 3 means 9 as composite number as in below table.
|
|
|
3
|
|
5
|
|
7
|
|
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
|
5 is the next prime number so we will make all multiple of 5 starting from square of 5 means 25 as composite number as in below table.
|
|
|
3
|
|
5
|
|
7
|
|
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
|
By this way you can mark all the composite number and remaining non-marked number would be prime number as below table
|
|
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
|
|
|
|
Java implementation of Seive of Eratosthenes
package com.techguy.algo;
/**
* @author techguylearning@gmail.com
*
*/
public class PrimeNumberSieveOfEratosthenes {
public static void main(String[] args) {
new PrimeNumberSieveOfEratosthenes().primeNumbers(100);
}
public void primeNumbers(int upperBound){
boolean isComposite[] = new boolean[upperBound + 1];
int upperBoundSqrt = (int)Math.sqrt(upperBound);
for (int i = 2; i <=upperBoundSqrt ; i++) {
if(!isComposite[i]){
for(int k = i*i; k < upperBound; k = k+i){
isComposite[k]=true;
}
}
}
for (int i = 2; i < upperBound; i++) {
if(!isComposite[i]){
System.out.print(i+" ");
}
}
}
}
Note:- This algorithm is marking some number more than one times as composite that is drawback of this algorithm.
