Given two numbers a and b as interval range, the task is to find the prime numbers in between this interval.
Examples:
Input : a = 1, b = 10
Output : 2, 3, 5, 7
Input : a = 10, b = 20
Output : 11, 13, 17, 19
In the below program, the range of numbers is taken as input and stored in the variables ‘a’ and ‘b’. Then using a for-loop, the numbers between the interval of a and b are traversed. For each number in the for loop, it is checked if this number is prime or not. If found prime, print the number. Then the next number in the loop is checked, till all numbers are checked.
Program:
C++
// C++ program to find the prime numbers// between a given interval#include <bits/stdc++.h>using namespace std;int main(){ // Declare the variables int a, b, i, j, flag; // Ask user to enter lower value of interval cout << "Enter lower bound of the interval: "; cin >> a; // Take input // Ask user to enter upper value of interval cout << "\nEnter upper bound of the interval: "; cin >> b; // Take input // Print display message cout << "\nPrime numbers between " << a << " and " << b << " are: "; // Traverse each number in the interval // with the help of for loop for (i = a; i <= b; i++) { // Skip 0 and 1 as they are // neither prime nor composite if (i == 1 || i == 0) continue; // flag variable to tell // if i is prime or not flag = 1; for (j = 2; j <= i / 2; ++j) { if (i % j == 0) { flag = 0; break; } } // flag = 1 means i is prime // and flag = 0 means i is not prime if (flag == 1) cout << i << " "; } return 0;}// This code is contributed by Akanksha Rai |
C
// C program to find the prime numbers// between a given interval#include <stdio.h>int main(){ // Declare the variables int a, b, i, j, flag; // Ask user to enter lower value of interval printf("Enter lower bound of the interval: "); scanf("%d", &a); // Take input // Ask user to enter upper value of interval printf("\nEnter upper bound of the interval: "); scanf("%d", &b); // Take input // Print display message printf("\nPrime numbers between %d and %d are: ", a, b); // Traverse each number in the interval // with the help of for loop for (i = a; i <= b; i++) { // Skip 0 and 1 as they are // neither prime nor composite if (i == 1 || i == 0) continue; // flag variable to tell // if i is prime or not flag = 1; for (j = 2; j <= i / 2; ++j) { if (i % j == 0) { flag = 0; break; } } // flag = 1 means i is prime // and flag = 0 means i is not prime if (flag == 1) printf("%d ", i); } return 0;} |
Java
import java.util.Scanner;// Java program to find the prime numbers// between a given intervalpublic class GFG { // driver code public static void main(String[] args) { Scanner sc = new Scanner(System.in); // Declare the variables int a, b, i, j, flag; // Ask user to enter lower value of interval System.out.printf("Enter lower bound of the interval: "); a = sc.nextInt(); // Take input // Ask user to enter upper value of interval System.out.printf("\nEnter upper bound of the interval: "); b = sc.nextInt(); // Take input // Print display message System.out.printf("\nPrime numbers between %d and %d are: ", a, b); // Traverse each number in the interval // with the help of for loop for (i = a; i <= b; i++) { // Skip 0 and 1 as they are // neither prime nor composite if (i == 1 || i == 0) continue; // flag variable to tell // if i is prime or not flag = 1; for (j = 2; j <= i / 2; ++j) { if (i % j == 0) { flag = 0; break; } } // flag = 1 means i is prime // and flag = 0 means i is not prime if (flag == 1) System.out.println(i); } }} |
Python3
# Python3 program to find the prime # numbers between a given intervalif __name__ == '__main__': # Declare the variables a, b, i, j, flag = 0, 0, 0, 0, 0 # Ask user to enter lower value of interval print("Enter lower bound of the interval:", end = "") a = int(input()) # Take input print(a) # Ask user to enter upper value of interval print("Enter upper bound of the interval:", end = "") b = int(input()) # Take input print(b) # Print display message print("Prime numbers between", a, "and", b, "are:", end = "") # Traverse each number in the interval # with the help of for loop for i in range(a, b + 1): # Skip 1 as1 is neither # prime nor composite if (i == 1): continue # flag variable to tell # if i is prime or not flag = 1 for j in range(2, i // 2 + 1): if (i % j == 0): flag = 0 break # flag = 1 means i is prime # and flag = 0 means i is not prime if (flag == 1): print(i, end = " ") # This code is contributed # by Mohit kumar 29 |
C#
// C# program to find the prime numbers// between a given intervalusing System;class GFG{// Driver code public static void Main(string[] args) { // Declare the variables int a, b, i, j, flag; // Ask user to enter lower value of interval Console.WriteLine("Enter lower bound of " + "the interval: "); // Take input a = int.Parse(Console.ReadLine()); // Ask user to enter upper value of interval Console.WriteLine("\nEnter upper bound " + "of the interval: "); // Take input b = int.Parse(Console.ReadLine()); // Print display message Console.WriteLine("\nPrime numbers between " + "{0} and {1} are: ", a, b); // Traverse each number in the interval // with the help of for loop for(i = a; i <= b; i++) { // Skip 0 and 1 as they are // neither prime nor composite if (i == 1 || i == 0) continue; // flag variable to tell // if i is prime or not flag = 1; for(j = 2; j <= i / 2; ++j) { if (i % j == 0) { flag = 0; break; } } // flag = 1 means i is prime // and flag = 0 means i is not prime if (flag == 1) Console.WriteLine(i); }}}// This code is contributed by jana_sayantan |
Javascript
<script>// JavaScript program to find the prime numbers// between a given interval// driver code // Declare the variables let a, b, i, j, flag; // Ask user to enter lower value of interval and take input a = window.prompt("Enter lower bound of the interval: "); // Ask user to enter upper value of interval and take input b = window.prompt("Enter upper bound of the interval: "); // Print display message console.log("Prime numbers between " + a + " and " + b << " are: "); // Traverse each number in the interval // with the help of for loop for (i = a; i <= b; i++) { // Skip 0 and 1 as they are // neither prime nor composite if (i == 1 || i == 0) continue; // flag variable to tell // if i is prime or not flag = 1; for (j = 2; j <= i / 2; ++j) { if (i % j == 0) { flag = 0; break; } } // flag = 1 means i is prime // and flag = 0 means i is not prime if (flag == 1) document.write(i," "); }// This code is contributed by shinjanpatra</script> |
Output:
Enter lower bound of the interval: 1
Enter upper bound of the interval: 10
Prime numbers between 1 and 10 are: 2 3 5 7
Time Complexity: O(N2), Where N is the difference between the range
Auxiliary Space: O(1)
Optimized Solution :
The idea is to use the fact that even numbers (except 2) are not primes.
C++
// C++ program to find the prime numbers// between a given interval#include <bits/stdc++.h>using namespace std;int main(){ // Declare the variables int a, b, i, j; // Ask user to enter lower value of interval // interval < 0 cannot be prime numbers cout << "Enter lower bound of the interval: "; cin >> a; // Take input // Ask user to enter upper value of interval cout << "\nEnter upper bound of the interval: "; cin >> b; // Take input // Print display message cout << "\nPrime numbers between " << a << " and " << b << " are: "; // Explicitly handling the cases when a is less than 2 // since 0 and 1 are not prime numbers if (a <= 2) { a = 2; if (b >= 2) { cout << a << " "; a++; } } // MAKING SURE THAT a IS ODD BEFORE WE BEGIN // THE LOOP if (a % 2 == 0) a++; // NOTE : WE TRAVERSE THROUGH ODD NUMBERS ONLY for (i = a; i <= b; i = i + 2) { // flag variable to tell // if i is prime or not bool flag = 1; // WE TRAVERSE TILL SQUARE ROOT OF j only. // (LARGEST POSSIBLE VALUE OF A PRIME FACTOR) for (j = 2; j * j <= i; ++j) { if (i % j == 0) { flag = 0; break; } } // flag = 1 means i is prime // and flag = 0 means i is not prime if (flag == 1){ if(i==1) continue; else cout << i << " "; } } return 0;} |
Java
import java.util.*;public class PrimeNumbersInRange { // function which checks whether a number is Prime or Not // If the number is prime, it returns true. Else, it returns false. public static boolean isPrime(int n) { // 0 and 1 are neither prime nor composite numbers if (n == 0 || n == 1) { return false; } // 2 is a prime number if (n == 2) { return true; } // every composite number has a prime factor // less than or equal to its square root. for (int i = 2; i * i <= n; i++) { if (n % i == 0) { return false; } } return true; } // Driver code public static void main(String[] args) { Scanner sc = new Scanner(System.in); // Ask user to enter lower value of interval System.out.print("Enter lower bound of the interval: "); int lower = sc.nextInt(); // Take input // Ask user to enter upper value of interval System.out.print("\nEnter upper bound of the interval: "); int upper = sc.nextInt(); // Take input // Print display message System.out.printf("\nPrime numbers between %d and %d are: ", lower, upper); for (int i = lower; i <= upper; i++) { if (isPrime(i)) { System.out.print(i + " "); } } sc.close(); }} |
Python3
# Python3 program to find the prime # numbers between a given interval if __name__ == '__main__': # Declare the variables a, b, i, j = 0, 0, 0, 0 # Ask user to enter lower value of interval print("Enter lower bound of the interval:",end = "") a = int(input()) # Take input print(a) # Ask user to enter upper value of interval print("Enter upper bound of the interval:",end = "") b = int(input()) # Take input print(b) # Print display message print("Prime numbers between", a, "and",b, "are:", end = "") # Explicitly handling the cases when a is less than 2 if (a == 1): print(a,end=" ") a+=1 if (b >= 2): print(a,end=" ") a+=1 if (a == 2): print(a,end=" ") # MAKING SURE THAT a IS ODD BEFORE WE BEGIN # THE LOOP if (a % 2 == 0): a+=1 # NOTE : WE TRAVERSE THROUGH ODD NUMBERS ONLY for i in range(a,b+1,2): # flag variable to tell # if i is prime or not flag = 1 # WE TRAVERSE TILL SQUARE ROOT OF j only. # (LARGEST POSSIBLE VALUE OF A PRIME FACTOR) j = 2 while(j * j <= i): if (i % j == 0): flag = 0 break j+=1 # flag = 1 means i is prime # and flag = 0 means i is not prime if (flag == 1): print(i,end=" ")# This code is contributed by shubhamsingh10 |
C#
// C# program to find the prime numbers// between a given intervalusing System;class GFG{ // Driver code static public void Main() { // Declare the variables int a, b, i, j, flag; // Ask user to enter lower value of interval Console.Write( "Enter lower bound of the interval: "); a = Convert.ToInt32( Console.ReadLine()); // Take input // Ask user to enter upper value of interval Console.Write( "\nEnter upper bound of the interval: "); b = Convert.ToInt32( Console.ReadLine()); // Take input // Print display message Console.Write("\nPrime numbers between " + a + " and " + b + " are: "); // Explicitly handling the cases when a is less than // 2 if (a == 1) { Console.Write(a + " "); a++; if (b >= 2) { Console.Write(a + " "); a++; } } if (a == 2) { Console.Write(a + " "); } // MAKING SURE THAT a IS ODD BEFORE WE BEGIN // THE LOOP if (a % 2 == 0) { a++; } // NOTE : WE TRAVERSE THROUGH ODD NUMBERS ONLY for (i = a; i <= b; i = i + 2) { // flag variable to tell // if i is prime or not flag = 1; // WE TRAVERSE TILL SQUARE ROOT OF j only. // (LARGEST POSSIBLE VALUE OF A PRIME FACTOR) for (j = 2; j * j <= i; ++j) { if (i % j == 0) { flag = 0; break; } } // flag = 1 means i is prime // and flag = 0 means i is not prime if (flag == 1) { Console.Write(i + " "); } } }}// This code is contributed by rag2127 |
Javascript
<script>// JavaScript program to find the prime numbers// between a given interval// driver code // Declare the variables let a, b, i, j; // Ask user to enter lower value of interval and take input a = window.prompt("Enter lower bound of the interval: "); // Ask user to enter upper value of interval and take input b = window.prompt("Enter upper bound of the interval: "); // Print display message console.log("Prime numbers between " + a + " and " + b << " are: "); // Explicitly handling the cases when a is less than 2 // since 0 and 1 are not prime numbers if (a <= 2) { a = 2; if (b >= 2) { document.write(a," "); a++; } } // MAKING SURE THAT a IS ODD BEFORE WE BEGIN // THE LOOP if (a % 2 == 0) a++; // NOTE : WE TRAVERSE THROUGH ODD NUMBERS ONLY for (i = a; i <= b; i = i + 2) { // flag variable to tell // if i is prime or not let flag = 1; // WE TRAVERSE TILL SQUARE ROOT OF j only. // (LARGEST POSSIBLE VALUE OF A PRIME FACTOR) for (j = 2; j * j <= i; ++j) { if (i % j == 0) { flag = 0; break; } } // flag = 1 means i is prime // and flag = 0 means i is not prime if (flag == 1){ if(i == 1) continue; else document.write(i, " "); } }// This code is contributed by shinjanpatra</script> |
Output:
Enter lower bound of the interval: 1
Enter upper bound of the interval: 10
Prime numbers between 1 and 10 are: 2 3 5 7
Time Complexity: O(N*sqrt(N)), Where N is the difference between the range
Auxiliary Space: O(1)
Sieve of Eratosthenes Method:
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.
Steps:
- Create a boolean array prime[srt to n] and initialize all its entries as true.
- Mark prime[0] and prime[1] as false because they are not prime numbers.
- Starting from p = srt, for each prime number p less than or equal to the square root of n, mark all multiples of p greater than or equal to p*p as composite by setting prime[i] to false.
- Finally, print all prime numbers between srt and n.
Below is the implementation:
C++
// C++ program to find the prime numbers// between a given interval using Sieve of Eratosthenes#include <bits/stdc++.h>using namespace std;void SieveOfEratosthenes(int srt, int n){ // Create a boolean array "prime[srt to n]" and // initialize all entries it as true. A value in // prime[i] will finally be false if i is Not a prime, // else true. bool prime[n + 2]; memset(prime, true, sizeof(prime)); prime[0] = false; prime[1] = false; for (int p = 2; p * p <= n; p++) { // If prime[p] is not changed, then it is a prime if (prime[p] == true) { // Update all multiples of p greater than or // equal to the square of it numbers which are // multiple of p and are less than p^2 are // already been marked. for (int i = p * p; i <= n; i += p) prime[i] = false; } } // Print all prime numbers for (int p = srt; p <= n; p++) if (prime[p]) cout << p << " ";}// Driver Codeint main(){ int srt = 1; int end = 10; SieveOfEratosthenes(srt, end); return 0;}// This code is contributed by Susobhan Akhuli |
Java
// java program to find the prime numbers// between a given interval using Sieve of Eratosthenesimport java.util.*;public class GFG { public static void SieveOfEratosthenes(int srt, int n) { // Create a boolean array "prime[srt to n]" and // initialize all entries it as true. A value in // prime[i] will finally be false if i is Not a // prime, else true. boolean[] prime = new boolean[n + 2]; Arrays.fill(prime, true); prime[0] = false; prime[1] = false; for (int p = 2; p * p <= n; p++) { // If prime[p] is not changed, then it is a // prime if (prime[p] == true) { // Update all multiples of p greater than or // equal to the square of it numbers which // are multiple of p and are less than p^2 // are already been marked. for (int i = p * p; i <= n; i += p) { prime[i] = false; } } } // Print all prime numbers for (int p = srt; p <= n; p++) { if (prime[p]) { System.out.print(p + " "); } } } // Driver Code public static void main(String[] args) { int srt = 1; int end = 10; SieveOfEratosthenes(srt, end); }}// This code is contributed by Susobhan Akhuli |
Python3
# Python program to find the prime numbers# between a given interval using Sieve of Eratosthenesimport mathdef SieveOfEratosthenes(srt, n): # Create a boolean array "prime[srt to n]" and # initialize all entries it as true. A value in # prime[i] will finally be false if i is Not a prime, # else true. prime = [True for i in range(n + 2 )] prime[0] = False prime[1] = False for p in range(2, int(math.sqrt(n))+1): # If prime[p] is not changed, then it is a prime if prime[p] == True: # Update all multiples of p greater than or # equal to the square of it numbers which are # multiple of p and are less than p^2 are # already been marked. for i in range(p*p, n+1, p): prime[i] = False # Print all prime numbers for p in range(srt, n+1): if prime[p]: print(p, end=" ")# Driver Codeif __name__ == "__main__": srt = 1 end = 10 SieveOfEratosthenes(srt, end)# This code is contributed by Susobhan Akhuli |
C#
// C# program to find the prime numbers// between a given interval using Sieve of Eratosthenesusing System;public class GFG{ public static void SieveOfEratosthenes(int srt, int n) { // Create a boolean array "prime[srt to n]" and // initialize all entries it as true. A value in // prime[i] will finally be false if i is Not a // prime, else true. bool[] prime = new bool[n + 2]; Array.Fill(prime, true); prime[0] = false; prime[1] = false; for (int p = 2; p * p <= n; p++) { // If prime[p] is not changed, then it is a // prime if (prime[p] == true) { // Update all multiples of p greater than or // equal to the square of it. Numbers which // are multiples of p and are less than p^2 // are already marked. for (int i = p * p; i <= n; i += p) { prime[i] = false; } } } // Print all prime numbers for (int p = srt; p <= n; p++) { if (prime[p]) { Console.Write(p + " "); } } } // Driver Code public static void Main(string[] args) { int srt = 1; int end = 10; SieveOfEratosthenes(srt, end); }}// This code is contributed by Pushpesh Raj |
Javascript
function SieveOfEratosthenes(srt, n) { // Create a boolean array "prime[srt to n]" and // initialize all entries it as true. A value in // prime[i] will finally be false if i is Not a prime, // else true. let prime = new Array(n + 2 ).fill(true); prime[0] = false; prime[1] = false; for (let p = 2; p * p <= n; p++) { // If prime[p] is not changed, then it is a prime if (prime[p] == true) { // Update all multiples of p greater than or // equal to the square of it numbers which are // multiple of p and are less than p^2 are // already been marked. for (let i = p * p; i <= n; i += p) prime[i] = false; } } // Print all prime numbers for (let p = srt; p <= n; p++) if (prime[p]) console.log(p + " ");}let srt = 1;let end = 10;SieveOfEratosthenes(srt, end); |
Output
2 3 5 7
Time Complexity:
The time complexity of the Sieve of Eratosthenes algorithm is O(n*log(log(n))) as it iterates over all numbers from 2 to n and removes all the multiples of each prime number.
In this code, the algorithm is applied only to a range [srt, n], which reduces the time complexity to O((n-srt+1)*log(log(n))) for the range [srt, n]. The loop for marking the multiples of each prime number iterates from p*p to n, which takes O((n-srt+1)*log(log(n))) time. Therefore, the overall time complexity of this code is O((n-srt+1)*log(log(n))).
Auxiliary Space:
The space complexity of the algorithm is O(n), which is the size of the boolean array prime. However, the size of the array is reduced to n+2-srt, which is the size of the array required for the given range [srt, n]. Therefore, the auxiliary space complexity of the code is O(n-srt+1).
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
