Count of all values of N in [ L , R ] such that count of primes upto N is also prime | Function to count the number of crazy primes in the given range [ L , R ] ; Stores all primes ; Stores count of primes ; Stores if frequency of primes is a prime or not upto each index ; Sieve of Eratosthenes ; Count primes ; If i is a prime ; Stores frequency of primes ; If the frequency of primes is a prime ; Increase count of required numbers ; Return the required count ; Driver Code ; Given Range ; Function Call
def count_crazy_primes ( L , R ) : NEW_LINE INDENT prime = [ 0 ] * ( R + 1 ) NEW_LINE countPrime = [ 0 ] * ( R + 1 ) NEW_LINE freqPrime = [ 0 ] * ( R + 1 ) NEW_LINE prime [ 0 ] = prime [ 1 ] = 1 NEW_LINE p = 2 NEW_LINE while p * p <= R : NEW_LINE INDENT if ( prime [ p ] == 0 ) : NEW_LINE INDENT for i in range ( p * p , R + 1 , p ) : NEW_LINE INDENT prime [ i ] = 1 NEW_LINE DEDENT DEDENT p += 1 NEW_LINE DEDENT for i in range ( 1 , R + 1 ) : NEW_LINE INDENT countPrime [ i ] = countPrime [ i - 1 ] NEW_LINE if ( not prime [ i ] ) : NEW_LINE INDENT countPrime [ i ] += 1 NEW_LINE DEDENT DEDENT for i in range ( 1 , R + 1 ) : NEW_LINE INDENT freqPrime [ i ] = freqPrime [ i - 1 ] NEW_LINE if ( not prime [ countPrime [ i ] ] ) : NEW_LINE INDENT freqPrime [ i ] += 1 NEW_LINE DEDENT DEDENT return ( freqPrime [ R ] - freqPrime [ L - 1 ] ) NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT L = 4 NEW_LINE R = 12 NEW_LINE print ( count_crazy_primes ( L , R ) ) NEW_LINE DEDENT