Count of all values of N in [ L , R ] such that count of primes upto N is also prime | C # implementation of the approach ; 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
using System ; class GFG { static int count_crazy_primes ( int L , int R ) { int [ ] prime = new int [ R + 1 ] ; int [ ] countPrime = new int [ R + 1 ] ; int [ ] freqPrime = new int [ R + 1 ] ; prime [ 0 ] = 1 ; prime [ 1 ] = 1 ; for ( int p = 2 ; p * p <= R ; p ++ ) { if ( prime [ p ] == 0 ) { for ( int i = p * p ; i <= R ; i += p ) prime [ i ] = 1 ; } } for ( int i = 1 ; i <= R ; i ++ ) { countPrime [ i ] = countPrime [ i - 1 ] ; if ( prime [ i ] != 0 ) { countPrime [ i ] ++ ; } } for ( int i = 1 ; i <= R ; i ++ ) { freqPrime [ i ] = freqPrime [ i - 1 ] ; if ( prime [ countPrime [ i ] ] != 0 ) { freqPrime [ i ] ++ ; } } return ( freqPrime [ R ] - freqPrime [ L - 1 ] ) ; } public static void Main ( String [ ] args ) { int L = 4 , R = 12 ; Console . WriteLine ( count_crazy_primes ( L , R ) ) ; } }