Generate all prime numbers between two given numbers. The task is to print prime numbers in that range. The Sieve of Eratosthenes is one of the most efficient ways to find all primes smaller than n where n is smaller than 10 million or so. Examples:
Input : start = 50 end = 100 Output : 53 59 61 67 71 73 79 83 89 97 Input : start = 900 end = 1000 Output : 907 911 919 929 937 941 947 953 967 971 977 983 991 997
Idea is to use Sieve of Eratosthenes as a subroutine. We have discussed one implementation in Prime numbers in a given range using STL | Set 1
- Find primes in the range from 0 to end and store it in a vector
- Find the index of element less than start value using binary search. We use lower_bound() in STL.
- Erase elements from the beginning of the vector to that index. We use vector erase()
Viola! The vector contains primes ranging from start to end.
CPP
// C++ program to print all primes// in a range using Sieve of Eratosthenes#include <algorithm>#include <cmath>#include <iostream>#include <vector>using namespace std;#define all(v) v.begin(), v.end()typedef unsigned long long int ulli;vector<ulli> sieve(ulli n){ // Create a boolean vector "prime[0..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. vector<bool> prime(n + 1, true); prime[0] = false; prime[1] = false; int m = sqrt(n); for (ulli p = 2; p <= m; p++) { // If prime[p] is not changed, then it // is a prime if (prime[p]) { // Update all multiples of p for (ulli i = p * 2; i <= n; i += p) prime[i] = false; } } // push all the primes into the vector ans vector<ulli> ans; for (int i = 0; i < n; i++) if (prime[i]) ans.push_back(i); return ans;}vector<ulli> sieveRange(ulli start, ulli end){ // find primes from [0..end] range vector<ulli> ans = sieve(end); // Find index of first prime greater than or // equal to start // O(sqrt(n)loglog(n)) int lower_bound_index = lower_bound(all(ans), start) - ans.begin(); // Remove all elements smaller than start. // O(logn) ans.erase(ans.begin(), ans.begin() + lower_bound_index); return ans;}// Driver Program to test above functionint main(void){ ulli start = 50; ulli end = 100; vector<ulli> ans = sieveRange(start, end); for (auto i : ans) cout << i << ' '; return 0;} |
Java
// Java program to print all primes// in a range using Sieve of Eratosthenesimport java.util.*;public class GFG { static int lower_bound(ArrayList<Long> list, long elem) { for (int i = 0; i < list.size(); i++) { if (list.get(i) >= elem) return i; } return list.size(); } static ArrayList<Long> sieve(long n) { // Create a boolean vector "prime[0..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. ArrayList<Boolean> prime = new ArrayList<Boolean>(); for (int i = 0; i <= n; i++) prime.add(true); prime.set(0, false); prime.set(1, false); int m = (int)Math.sqrt(n); for (int p = 2; p <= m; p++) { // If prime[p] is not changed, then it // is a prime if (prime.get(p)) { // Update all multiples of p for (int i = p * 2; i <= n; i += p) prime.set(i, false); } } // push all the primes into the vector ans ArrayList<Long> ans = new ArrayList<Long>(); for (int i = 0; i < n; i++) if (prime.get(i)) ans.add((long)i); return ans; } static ArrayList<Long> sieveRange(long start, long end) { // find primes from [0..end] range ArrayList<Long> ans = sieve(end); // Find index of first prime greater than or // equal to start // O(sqrt(n)loglog(n)) int lower_bound_index = lower_bound(ans, start); // Remove all elements smaller than start. // O(logn) for (int i = 0; i < lower_bound_index; i++) ans.remove(0); return ans; } // Driver Program to test above function public static void main(String[] args) { long start = 50; long end = 100; ArrayList<Long> ans = sieveRange(start, end); for (Long i : ans) System.out.print(i + ", "); }}// This code is contributed by phasing17 |
Python3
# Python3 program to print all primes# in a range using Sieve of Eratosthenesdef lower_bound(arr, elem): for i in range(len(arr)): if (arr[i] >= elem): return i; return len(arr)def sieve(n): # Create a boolean vector "prime[0..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 + 1)] prime[0] = False; prime[1] = False; m = n ** 0.5 for p in range(2, int(m) + 1): # If prime[p] is not changed, then it # is a prime if (prime[p]): # Update all multiples of p for i in range(p + p, n + 1, p): prime[i] = False; # push all the primes into the vector ans ans = []; for i in range(n): if (prime[i]): ans.append(i); return ans;def sieveRange(start, end): # find primes from [0..end] range ans = sieve(end); # Find index of first prime greater than or # equal to start # O(sqrt(n)loglog(n)) lower_bound_index = lower_bound(ans, start); # Remove all elements smaller than start. # O(logn) ans = ans[lower_bound_index :] return ans;# Driver Program to test above functionstart = 50;end = 100;ans = sieveRange(start, end);print(ans);# This code is contributed by phasing17 |
C#
// C# program to print all primes// in a range using Sieve of Eratosthenesusing System;using System.Collections.Generic;class GFG{ static int lower_bound(List<long> list, long elem) { for (int i = 0; i < list.Count; i++) { if (list[i] >= elem) return i; } return list.Count; } static List<long> sieve(long n) { // Create a boolean vector "prime[0..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. List<bool> prime = new List<bool>(); for (int i = 0; i <= n; i++) prime.Add(true); prime[0] = false; prime[1] = false; int m = (int)Math.Sqrt(n); for (int p = 2; p <= m; p++) { // If prime[p] is not changed, then it // is a prime if (prime[p]) { // Update all multiples of p for (int i = p * 2; i <= n; i += p) prime[i] = false; } } // push all the primes into the vector ans List<long> ans = new List<long>(); for (int i = 0; i < n; i++) if (prime[i]) ans.Add(i); return ans; } static List<long> sieveRange(long start, long end) { // find primes from [0..end] range List<long> ans = sieve(end); // Find index of first prime greater than or // equal to start // O(sqrt(n)loglog(n)) int lower_bound_index = lower_bound(ans, start); // Remove all elements smaller than start. // O(logn) for (int i = 0; i < lower_bound_index; i++) ans.RemoveAt(0); return ans; } // Driver Program to test above function public static void Main(string[] args) { long start = 50; long end = 100; List<long> ans = sieveRange(start, end); foreach (var i in ans) Console.Write(i + ", "); }}// This code is contributed by phasing17 |
Javascript
// JavaScript program to print all primes// in a range using Sieve of Eratosthenesfunction lower_bound(arr, elem){ for (var i = 0; i < arr.length; i++) if (arr[i] >= elem) return i; return arr.length;}function sieve(n){ // Create a boolean vector "prime[0..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 + 1).fill(true); prime[0] = false; prime[1] = false; let m = Math.sqrt(n); for (let p = 2; p <= m; p++) { // If prime[p] is not changed, then it // is a prime if (prime[p]) { // Update all multiples of p for (let i = p * 2; i <= n; i += p) prime[i] = false; } } // push all the primes into the vector ans let ans = []; for (let i = 0; i < n; i++) if (prime[i]) ans.push(i); return ans;}function sieveRange(start, end){ // find primes from [0..end] range let ans = sieve(end); // Find index of first prime greater than or // equal to start // O(sqrt(n)loglog(n)) let lower_bound_index = lower_bound(ans, start); // Remove all elements smaller than start. // O(logn) ans = ans.slice(lower_bound_index, ans.length) return ans;}// Driver Program to test above functionlet start = 50;let end = 100;let ans = sieveRange(start, end);console.log(ans);// THis code is contributed by phasing17 |
Output:
53 59 61 67 71 73 79 83 89 97
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!
