Count of Double Prime numbers in a given range L to R | Java 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 ; Array to find double prime ; Function to find the number double prime numbers in range ; Assume all numbers as prime ; Check if the number is prime ; check for multiples of i ; Make all multiples of ith prime as non - prime ; Check if number at ith position is prime then increment count ; Indicates count of numbers from 1 to i that are also prime and hence double prime ; If number is not a double prime ; finding cumulative sum ; Driver code
import java . util . * ; import java . lang . * ; class GFG { static int [ ] arr = new int [ 1000001 ] ; static int [ ] dp = new int [ 1000001 ] ; static void count ( ) { int maxN = 1000000 , i , j ; for ( i = 0 ; i < maxN ; i ++ ) arr [ i ] = 1 ; arr [ 0 ] = 0 ; arr [ 1 ] = 0 ; for ( i = 2 ; i * i <= maxN ; i ++ ) { if ( arr [ i ] == 1 ) { for ( j = 2 * i ; j <= maxN ; j += i ) { arr [ j ] = 0 ; } } } int cnt = 0 ; for ( i = 0 ; i <= maxN ; i ++ ) { if ( arr [ i ] == 1 ) cnt ++ ; if ( arr [ cnt ] == 1 ) dp [ i ] = 1 ; else dp [ i ] = 0 ; } for ( i = 1 ; i <= maxN ; i ++ ) dp [ i ] += dp [ i - 1 ] ; } public static void main ( String [ ] args ) { int L = 4 , R = 12 ; count ( ) ; System . out . println ( dp [ R ] - dp [ L - 1 ] ) ; } }