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 Rangeimport 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 Rangeimport 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 Methodimport 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