1class SieveOfEratosthenes
2{
3 void sieveOfEratosthenes(int n)
4 {
5 // Create a boolean array "prime[0..n]" and initialize
6 // all entries it as true. A value in prime[i] will
7 // finally be false if i is Not a prime, else true.
8 boolean prime[] = new boolean[n+1];
9 for(int i=0;i<n;i++)
10 prime[i] = true;
11
12 for(int p = 2; p*p <=n; p++)
13 {
14 // If prime[p] is not changed, then it is a prime
15 if(prime[p] == true)
16 {
17 // Update all multiples of p
18 for(int i = p*p; i <= n; i += p)
19 prime[i] = false;
20 }
21 }
22
23 // Print all prime numbers
24 for(int i = 2; i <= n; i++)
25 {
26 if(prime[i] == true)
27 System.out.print(i + " ");
28 }
29 }
30
31 // Driver Program to test above function
32 public static void main(String args[])
33 {
34 int n = 30;
35 System.out.print("Following are the prime numbers ");
36 System.out.println("smaller than or equal to " + n);
37 SieveOfEratosthenes g = new SieveOfEratosthenes();
38 g.sieveOfEratosthenes(n);
39 }
40}