Java Program to Implement wheel Sieve to Generate Prime Numbers Between Given Range

0 0 3 minutes read

A prime number is a whole number greater than 1, which is only divisible by 1 and itself. The first few prime numbers are 2 3 5 7 11 13 17 19 23. Given a range, L to R, the task is to generate all the prime numbers that exist in the Range.

Examples

Input: 1 10
Output 2 3 5 7

Input: 20 30 
Output: 23 29

Approach 1: Check every element whether the element is prime or not.

Iterate in the Range L to R
Check every element whether the element is prime or not
Print the prime numbers in the range

Example

Java

// Java Program to Implement wheel Sieve to Generate Prime
// Numbers Between Given Range
 
import java.io.*;
 
class GFG {
    static boolean checkPrime(int n)
    {
        // Handling the edge case
        if (n == 1) {
            return false;
        }
        for (int i = 2; i <= Math.sqrt(n); ++i) {
 
            // checking the prime number
            if (n % i == 0) {
                return false;
            }
        }
 
        return true;
    }
    public static void main(String[] args)
    {
        // starting in a range
        int L = 1;
 
        // ending in a range
        int R = 20;
 
        for (int i = L; i <= R; ++i) {
 
            // printing the prime number
            if (checkPrime(i) == true) {
                System.out.print(i + " ");
            }
        }
    }
}

Output

2 3 5 7 11 13 17 19

Time Complexity: O(n * sqrt(n))
Space Complexity: O(1)

Approach 2: Using Sieve of Eratosthenes to Generate all the prime numbers

Generate all the prime numbers using Sieve of Eratosthenes (Refer this article)
Mark all the multiples of all prime numbers remaining numbers are left Prime numbers
Till the maximum range of the Value
Print all the prime numbers in the Given Range

Example

Java

// Java Program to Implement wheel Sieve to Generate Prime
// Numbers Between Given Range
 
import java.io.*;
 
class GFG {
 
    // Maximum range
    static boolean max[] = new boolean[1000001];
    static void fill()
    {
        // Maximum Range
        int n = 1000000;
 
        // Mark all numbers as a prime
        for (int i = 2; i <= n; ++i) {
            max[i] = true;
        }
        for (int i = 2; i <= Math.sqrt(n); ++i) {
 
            // if number is prime
            if (max[i] == true) {
 
                // mark all the factors
                // of i non prime
                for (int j = i * i; j <= n; j += i) {
                    max[j] = false;
                }
            }
        }
    }
 
    static void range(int L, int R)
    {
        for (int i = L; i <= R; ++i) {
 
            // checking the prime number
            if (max[i] == true) {
                // print the prime number
                System.out.print(i + " ");
            }
        }
    }
    public static void main(String[] args)
    {
        // starting in a range
        int L = 20;
 
        // ending in a range
        int R = 40;
 
        // mark all the numbers
        fill();
 
        // printing the prime numbers in range
        range(L, R);
    }
}

Output

23 29 31 37

Time Complexity: O(nlog(logn)
Space Complexity: O(1)

Approach 3: Using wheel Sieve to Generate all the Prime numbers. This approach is a very much optimized approach than discussed above approach. In this approach, we use the wheel Factorization method to find the prime numbers in a given range.

Example

Java

// Java program to check if the
// given number is prime using
// Wheel Factorization Method
 
import java.util.*;
 
class GFG {
 
    // Function to check if a given
    // number x is prime or not
    static boolean isPrime(int N)
    {
        boolean isPrime = true;
 
        // The Wheel for checking
        // prime number
        int[] arr = { 7, 11, 13, 17, 19, 23, 29, 31 };
 
        // Base Case
        if (N < 2) {
            isPrime = false;
        }
 
        // Check for the number taken
        // as basis
        if (N % 2 == 0 || N % 3 == 0 || N % 5 == 0) {
            isPrime = false;
        }
 
        // Check for Wheel
        // Here i, acts as the layer
        // of the wheel
        for (int i = 0; i < Math.sqrt(N); i += 30) {
 
            // Check for the list of
            // Sieve in arr[]
            for (int c : arr) {
 
                // If number is greater
                // than sqrt(N) break
                if (c > Math.sqrt(N)) {
                    break;
                }
 
                // Check if N is a multiple
                // of prime number in the
                // wheel
                else {
                    if (N % (c + i) == 0) {
                        isPrime = false;
                        break;
                    }
                }
 
                // If at any iteration
                // isPrime is false,
                // break from the loop
                if (!isPrime)
                    break;
            }
        }
 
        if (isPrime)
            return true;
        else
            return false;
    }
 
    // Driver's Code
    public static void main(String args[])
    {
 
        // Range
        int L = 10;
        int R = 20;
        for (int i = L; i <= R; ++i) {
 
            // Function call for primality
            // check
 
            // if true
            if (isPrime(i) == true) {
 
                // print the prime number
                System.out.print(i + " ");
            }
        }
    }
}