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 + " ");            }        }    }} |
Â
Â
Output
11 13 17 19
Â
