text: Count of interesting primes upto N | C ++ program to find the number of interesting primes up to N . ; Function to find all prime numbers ; Create a boolean array " prime [ 0 . . n ] " and initialize all entries as true . A value in prime [ i ] will finally be false if i is Not a prime . ; If prime [ p ] is not changed , then it is a prime ; Update all multiples of p greater than or equal to the square of it ; Store all prime numbers ; Function to check if a number is perfect square or not ; To store all primes ; To store all interseting primes ; Store all perfect squares ; Store all perfect quadruples ; Store all interseting primes ; Return count of interseting primes ; Driver code
code: #include <bits/stdc++.h> NEW_LINE using namespace std ; void SieveOfEratosthenes ( int n , unordered_set < int > & allPrimes ) { bool prime [ n + 1 ] ; memset ( prime , true , sizeof ( prime ) ) ; for ( int p = 2 ; p * p <= n ; p ++ ) { if ( prime [ p ] == true ) { for ( int i = p * p ; i <= n ; i += p ) prime [ i ] = false ; } } for ( int p = 2 ; p <= n ; p ++ ) if ( prime [ p ] ) allPrimes . insert ( p ) ; } int countInterestingPrimes ( int n ) { unordered_set < int > allPrimes ; SieveOfEratosthenes ( n , allPrimes ) ; unordered_set < int > intersetingPrimes ; vector < int > squares , quadruples ; for ( int i = 1 ; i * i <= n ; i ++ ) { squares . push_back ( i * i ) ; } for ( int i = 1 ; i * i * i * i <= n ; i ++ ) { quadruples . push_back ( i * i * i * i ) ; } for ( auto a : squares ) { for ( auto b : quadruples ) { if ( allPrimes . count ( a + b ) ) intersetingPrimes . insert ( a + b ) ; } } return intersetingPrimes . size ( ) ; } int main ( ) { int N = 10 ; cout << countInterestingPrimes ( N ) ; return 0 ; }