# Sieve of Eratosthenes - print all primes smaller than or equal to number n.

Sun Feb 06 2022 05:18:47 GMT+0000 (Coordinated Universal Time)

```// Shorter Implementation of the optimized sieve :

import java.io.*;
import java.util.*;

public class Main {

static void sieve(int n)
{
if(n <= 1)
return;

boolean isPrime[] = new boolean[n+1];

Arrays.fill(isPrime, true);

for(int i=2; i <= n; i++)
{
if(isPrime[i])
{
System.out.print(i+" ");
for(int j = i*i; j <= n; j = j+i)
{
isPrime[j] = false;
}
}
}
}

public static void main (String[] args) {

int n = 23;

sieve(n);

}
}

//Optimized Implementation : Time Complexity : O(nloglogn), Auxiliary Space : O(n)

static void sieve(int n)
{
if(n <= 1)
return;

boolean isPrime[] = new boolean[n+1];

Arrays.fill(isPrime, true);

for(int i=2; i*i <= n; i++)
{
if(isPrime[i])
{
for(int j = i*i; j <= n; j = j+i) // Replaced 2*i by i*i
{
isPrime[j] = false;
}
}
}

for(int i = 2; i<=n; i++)
{
if(isPrime[i])
System.out.print(i+" ");
}
}

//Simple Implementation of Sieve :

static void sieve(int n)
{
if(n <= 1)
return;

boolean isPrime[] = new boolean[n+1];

Arrays.fill(isPrime, true);

for(int i=2; i*i <= n; i++)
{
if(isPrime[i])
{
for(int j = 2*i; j <= n; j = j+i)
{
isPrime[j] = false;
}
}
}

for(int i = 2; i<=n; i++)
{
if(isPrime[i])
System.out.print(i+" ");
}
}

//Naive Solution : Time Complexity : O(n(sqrt(n))

static boolean isPrime(int n)
{
if(n==1)
return false;

if(n==2 || n==3)
return true;

if(n%2==0 || n%3==0)
return false;

for(int i=5; i*i<=n; i=i+6)
{
if(n % i == 0 || n % (i + 2) == 0)
return false;
}

return true;
}

static void printPrimes(int n)
{
for(int i = 2; i<=n; i++)
{
if(isPrime[i])
System.out.print(i+" ");
}
}```
content_copyCOPY

Given a number n, print all primes smaller than or equal to n. Following is the algorithm to find all the prime numbers less than or equal to a given integer n by the Eratosthenes method: When the algorithm terminates, all the numbers in the list that are not marked are prime. Explanation with Example: Let us take an example when n = 50. So we need to print all prime numbers smaller than or equal to 50. We create a list of all numbers from 2 to 50. STEP-1: According to the algorithm we will mark all the numbers which are divisible by 2 and are greater than or equal to the square of it. STEP-2: Now we move to our next unmarked number 3 and mark all the numbers which are multiples of 3 and are greater than or equal to the square of it. STEP-3: We move to our next unmarked number 5 and mark all multiples of 5 and are greater than or equal to the square of it. STEP-4: We continue this process and our final table will look like below: STEP-5: So, the prime numbers are the unmarked ones: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47.