# Count of Double Prime numbers in a given range L to R

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 primewhen the count of prime numbers in the range 1 to N(excluding 1 and including N)is also prime.Attention reader! Don’t stop learning now. Get hold of all the important mathematical concepts for competitive programming with the

Essential Maths for CP Courseat a student-friendly price. To complete your preparation from learning a language to DS Algo and many more, please referComplete Interview Preparation Course.

**Examples:**

Input:L = 3, R = 10Output:4Explanation:

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 = 12Output:5Explanation:

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 10
^{6}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 prime` `int` `arr[1000001];` `// Array to find double prime` `int` `dp[1000001];` `// Function to find the number` `// double prime numbers in range` `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 code` `int` `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 R` `import` `java.util.*;` `import` `java.lang.*;` `class` `GFG{` ` ` `// Array to make Sieve` `// where arr[i]=0 indicates` `// non prime and arr[i] = 1` `// indicates prime` `static` `int` `[] arr = ` `new` `int` `[` `1000001` `];` `// Array to find double prime` `static` `int` `[] dp = ` `new` `int` `[` `1000001` `];` `// Function to find the number` `// double prime numbers in range` `static` `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 code` `public` `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 prime` `arr ` `=` `[` `0` `] ` `*` `1000001` `# Array to find double prime` `dp ` `=` `[` `0` `] ` `*` `1000001` `# Function to find the number` `# double prime numbers in range` `def` `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 code` `L ` `=` `4` `R ` `=` `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 R` `using` `System;` `class` `GFG{` ` ` `// Array to make Sieve` `// where arr[i]=0 indicates` `// non prime and arr[i] = 1` `// indicates prime` `static` `int` `[] arr = ` `new` `int` `[1000001];` `// Array to find double prime` `static` `int` `[] dp = ` `new` `int` `[1000001];` `// Function to find the number` `// double prime numbers in range` `static` `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 code` `public` `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 prime` `let arr = [];` ` ` `// Array to find double prime` `let dp = [];` ` ` `// Function to find the number` `// double prime numbers in range` `function` `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