Java Program to Implement Sieve of Eratosthenes to Generate Prime Numbers Between Given Range

A number which is divisible by 1 and itself or a number which has factors as 1 and the number itself is called a prime number. The sieve of Eratosthenes is one of the most efficient ways to find all primes smaller than n when n is smaller than 10 million or so.

Example:

Input : from = 1, to = 20 Output: 2 3 5 7 11 13 17 19 Input : from = 4, to = 15 Output: 5 7 11 13

A. Naive approach:

1. Define a function named isprime(int n) which will check if a number is prime or not.
2. Run a loop from "from" to "to".
3. Inside for loop, check if i is prime, then print the value of i

Below is the implementation of the above approach:

// Java Program to Generate Prime // Numbers Between Given Range class GFG {  public static boolean isprime(int n)  {  if (n == 1)  return false;  for (int i = 2; i <= Math.sqrt(n); i++)  // Check if a number has factors  // its not prime and return 0  if (n % i == 0)  return false;    // Check if a number dont   // have any factore  // its prime and return 1  return true;  }  public static void main(String[] args)  {    // Suppose we want to print  // prime no. from 1 to 20  int from = 1, to = 20, k = 0;  for (int i = from; i <= to; i++)  if (isprime(i))  System.out.print(" " + i);  } } 

 2 3 5 7 11 13 17 19

Time complexity: O(n^3/2)

Auxiliary space: O(1) as it is using constant space for variables

B. Sieve of Eratosthenes:

Initially, assume every number from 0 to n is prime, assign array value of each number as 1. After that, strike off each non-prime number by changing the value from 1 to 0 in an array and finally, print only those numbers whose array value is 1, i.e. prime numbers.

Approach: 

1. Input n from user
2. In array, fill 1 corresponding to each element
3. Do a[0]=0 and a[1]=0 as we know 0,1 are not prime
4. Assume 1st number(2) to be prime and strike off the multiples of 2(as the multiples of 2 will be non-prime)
5. Continue step 3 till square root(n)
6. Print the list containing non-striked (or prime) numbers.

Below is the implementation of the above approach: 

// Java Program to Implement  // Sieve of eratosthenes // to Generate Prime Numbers  // Between Given Range import java.util.*; class GFG {  public static void main(String[] args)  {  int from = 1, to = 20, i;  boolean[] a = new boolean[to + 1];  Arrays.fill(a, true);  // 0 and 1 are not prime  a[0] = false;  a[1] = false;  for (i = 2; i <= Math.sqrt(to); i++)  // Check if number is prime  if (a[i])  for (int j = i * i; j <= to; j += i) {  a[j] = false;  }  for (i = from; i <= to; i++) {  // Printing only prime numbers  if (a[i])  System.out.print(" " + i);  }  } } 

 2 3 5 7 11 13 17 19

Time Complexity: O(n log(log n))

Auxiliary Space: O(n)