Count of Double Prime numbers in a given 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
arr = [ 0 ] * 1000001 NEW_LINE dp = [ 0 ] * 1000001 NEW_LINE def count ( ) : NEW_LINE INDENT maxN = 1000000 NEW_LINE for i in range ( 0 , maxN ) : NEW_LINE INDENT arr [ i ] = 1 NEW_LINE DEDENT arr [ 0 ] = 0 NEW_LINE arr [ 1 ] = 0 NEW_LINE i = 2 NEW_LINE while ( i * i <= maxN ) : NEW_LINE INDENT if ( arr [ i ] == 1 ) : NEW_LINE INDENT for j in range ( 2 * i , maxN + 1 , i ) : NEW_LINE INDENT arr [ j ] = 0 NEW_LINE DEDENT DEDENT i += 1 NEW_LINE DEDENT cnt = 0 NEW_LINE for i in range ( 0 , maxN + 1 ) : NEW_LINE INDENT if ( arr [ i ] == 1 ) : NEW_LINE INDENT cnt += 1 NEW_LINE DEDENT if ( arr [ cnt ] == 1 ) : NEW_LINE INDENT dp [ i ] = 1 NEW_LINE DEDENT else : NEW_LINE INDENT dp [ i ] = 0 NEW_LINE DEDENT DEDENT for i in range ( 0 , maxN + 1 ) : NEW_LINE INDENT dp [ i ] += dp [ i - 1 ] NEW_LINE DEDENT DEDENT L = 4 NEW_LINE R = 12 NEW_LINE count ( ) NEW_LINE print ( dp [ R ] - dp [ L - 1 ] ) NEW_LINE