Given two integers L and R, the task to find the number of Double Prime numbers in the range.
A number N is called double prime when the count of prime numbers in the range 1 to N (excluding 1 and including N) is also prime.
Examples:
Input: L = 3, R = 10
Output: 4
Explanation:
For 3, we have the range 1, 2, 3, and count of prime number is 2 (which is also a prime no.)
For 4, we have the range 1, 2, 3, 4, and count of a prime number is 2 (which is also a prime no.)
For 5, we have the range 1, 2, 3, 4, 5, and count of a prime number is 3 (which is also a prime no.)
For 6, we have the range 1, 2, 3, 4, 5, 6, and count of prime numbers is 3 (which is also a prime no.)
For 7, we have the range 1, 2, 3, 4, 5, 6, 7, and count of prime numbers is 4 which is nonprime.
Similarly for other numbers till R = 10, the count of prime numbers is nonprime. Hence the count of double prime numbers is 4.
Input: L = 4, R = 12
Output: 5
Explanation:
For the given range there are total 5 double prime numbers.
Approach:
To solve the problem mentioned above we will use the concept of Sieve to generate prime numbers.
- Generate all prime numbers for 0 to 106 and store in an array.
- Initialize a variable count to keep a track of prime numbers from 1 to some ith position.
- Then for every prime number we will increment the count and also set dp[count] = 1 (where dp is the array which stores a double prime number) indicating the number of numbers from 1 to some ith position that are prime.
- Lastly, find the cumulative sum of dp array so the answer will be dp[R] – dp[L – 1].
Below is the implementation of the above approach:
C++
// C++ program to find the count// of Double Prime numbers// in the range L to R#include <bits/stdc++.h>using namespace std;// Array to make Sieve// where arr[i]=0 indicates// non prime and arr[i] = 1// indicates primeint arr[1000001];// Array to find double primeint dp[1000001];// Function to find the number// double prime numbers in rangevoid count(){ int maxN = 1000000, i, j; // Assume all numbers as prime for (i = 0; i < maxN; i++) arr[i] = 1; arr[0] = 0; arr[1] = 0; for (i = 2; i * i <= maxN; i++) { // Check if the number is prime if (arr[i] == 1) { // check for multiples of i for (j = 2 * i; j <= maxN; j += i) { // Make all multiples of // ith prime as non-prime arr[j] = 0; } } } int cnt = 0; for (i = 0; i <= maxN; i++) { // Check if number at ith position // is prime then increment count if (arr[i] == 1) cnt++; if (arr[cnt] == 1) // Indicates count of numbers // from 1 to i that are // also prime and // hence double prime dp[i] = 1; else // If number is not a double prime dp[i] = 0; } for (i = 1; i <= maxN; i++) // finding cumulative sum dp[i] += dp[i - 1];}// Driver codeint main(){ int L = 4, R = 12; count(); cout << dp[R] - dp[L - 1]; return 0;} |
Java
// Java program to find the count// of Double Prime numbers// in the range L to Rimport java.util.*;import java.lang.*;class GFG{ // Array to make Sieve// where arr[i]=0 indicates// non prime and arr[i] = 1// indicates primestatic int[] arr = new int[1000001];// Array to find double primestatic int[] dp = new int[1000001];// Function to find the number// double prime numbers in rangestatic void count(){ int maxN = 1000000, i, j; // Assume all numbers as prime for (i = 0; i < maxN; i++) arr[i] = 1; arr[0] = 0; arr[1] = 0; for (i = 2; i * i <= maxN; i++) { // Check if the number is prime if (arr[i] == 1) { // check for multiples of i for (j = 2 * i; j <= maxN; j += i) { // Make all multiples of // ith prime as non-prime arr[j] = 0; } } } int cnt = 0; for (i = 0; i <= maxN; i++) { // Check if number at ith position // is prime then increment count if (arr[i] == 1) cnt++; if (arr[cnt] == 1) // Indicates count of numbers // from 1 to i that are // also prime and // hence double prime dp[i] = 1; else // If number is not a double prime dp[i] = 0; } for (i = 1; i <= maxN; i++) // finding cumulative sum dp[i] += dp[i - 1];}// Driver codepublic static void main(String[] args){ int L = 4, R = 12; count(); System.out.println(dp[R] - dp[L - 1]);}}// This code is contributed by offbeat |
Python3
# Python3 program to find the count# of Double Prime numbers# in the range L to R# Array to make Sieve# where arr[i]=0 indicates# non prime and arr[i] = 1# indicates primearr = [0] * 1000001# Array to find double primedp = [0] * 1000001# Function to find the number# double prime numbers in rangedef count(): maxN = 1000000 # Assume all numbers as prime for i in range(0, maxN): arr[i] = 1 arr[0] = 0 arr[1] = 0 i = 2 while(i * i <= maxN): # Check if the number is prime if (arr[i] == 1): # Check for multiples of i for j in range(2 * i, maxN + 1, i): # Make all multiples of # ith prime as non-prime arr[j] = 0 i += 1 cnt = 0 for i in range(0, maxN + 1): # Check if number at ith position # is prime then increment count if (arr[i] == 1): cnt += 1 if (arr[cnt] == 1): # Indicates count of numbers # from 1 to i that are # also prime and # hence double prime dp[i] = 1 else: # If number is not a double prime dp[i] = 0 for i in range(0, maxN + 1): # Finding cumulative sum dp[i] += dp[i - 1]# Driver codeL = 4R = 12 count()print(dp[R] - dp[L - 1])# This code is contributed by sanjoy_62 |
C#
// C# program to find the count// of Double Prime numbers// in the range L to Rusing System;class GFG{ // Array to make Sieve// where arr[i]=0 indicates// non prime and arr[i] = 1// indicates primestatic int[] arr = new int[1000001];// Array to find double primestatic int[] dp = new int[1000001];// Function to find the number// double prime numbers in rangestatic void count(){ int maxN = 1000000, i, j; // Assume all numbers as prime for (i = 0; i < maxN; i++) arr[i] = 1; arr[0] = 0; arr[1] = 0; for (i = 2; i * i <= maxN; i++) { // Check if the number is prime if (arr[i] == 1) { // check for multiples of i for (j = 2 * i; j <= maxN; j += i) { // Make all multiples of // ith prime as non-prime arr[j] = 0; } } } int cnt = 0; for (i = 0; i <= maxN; i++) { // Check if number at ith position // is prime then increment count if (arr[i] == 1) cnt++; if (arr[cnt] == 1) // Indicates count of numbers // from 1 to i that are // also prime and // hence double prime dp[i] = 1; else // If number is not a double prime dp[i] = 0; } for (i = 1; i <= maxN; i++) // finding cumulative sum dp[i] += dp[i - 1];}// Driver codepublic static void Main(){ int L = 4, R = 12; count(); Console.Write(dp[R] - dp[L - 1]);}}// This code is contributed by Code_Mech |
Javascript
<script> // Javascript program to find the count// of Double Prime numbers// in the range L to R// Array to make Sieve// where arr[i]=0 indicates// non prime and arr[i] = 1// indicates primelet arr = []; // Array to find double primelet dp = []; // Function to find the number// double prime numbers in rangefunction count(){ let maxN = 1000000, i, j; // Assume all numbers as prime for (i = 0; i < maxN; i++) arr[i] = 1; arr[0] = 0; arr[1] = 0; for (i = 2; i * i <= maxN; i++) { // Check if the number is prime if (arr[i] == 1) { // check for multiples of i for (j = 2 * i; j <= maxN; j += i) { // Make all multiples of // ith prime as non-prime arr[j] = 0; } } } let cnt = 0; for (i = 0; i <= maxN; i++) { // Check if number at ith position // is prime then increment count if (arr[i] == 1) cnt++; if (arr[cnt] == 1) // Indicates count of numbers // from 1 to i that are // also prime and // hence double prime dp[i] = 1; else // If number is not a double prime dp[i] = 0; } for (i = 1; i <= maxN; i++) // finding cumulative sum dp[i] += dp[i - 1];} // Driver code let L = 4, R = 12; count(); document.write(dp[R] - dp[L - 1]); // This code is contributed by susmitakundugoaldanga.</script> |
Output:
5
Time Complexity: O((R-L)*log(log(R)))
Auxiliary Space: O(R)
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!
