Count of all values of N in [ L , R ] such that count of primes upto N is also prime | C ++ program for the above 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; int count_crazy_primes ( int L , int R ) { int prime [ R + 1 ] = { 0 } ; int countPrime [ R + 1 ] = { 0 } ; int freqPrime [ R + 1 ] = { 0 } ; prime [ 0 ] = 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 ] ) { countPrime [ i ] ++ ; } } for ( int i = 1 ; i <= R ; i ++ ) { freqPrime [ i ] = freqPrime [ i - 1 ] ; if ( ! prime [ countPrime [ i ] ] ) { freqPrime [ i ] ++ ; } } return ( freqPrime [ R ] - freqPrime [ L - 1 ] ) ; } int main ( ) { int L = 4 , R = 12 ; cout << count_crazy_primes ( L , R ) ; return 0 ; }