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 bool 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: using System ; using System . Collections . Generic ; class GFG { static void SieveOfEratosthenes ( int n , HashSet < int > allPrimes ) { bool [ ] prime = new bool [ n + 1 ] ; for ( int i = 0 ; i < n + 1 ; i ++ ) prime [ i ] = true ; 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 . Add ( p ) ; } static int countInterestingPrimes ( int n ) { HashSet < int > allPrimes = new HashSet < int > ( ) ; SieveOfEratosthenes ( n , allPrimes ) ; HashSet < int > intersetingPrimes = new HashSet < int > ( ) ; List < int > squares = new List < int > ( ) , quadruples = new List < int > ( ) ; for ( int i = 1 ; i * i <= n ; i ++ ) { squares . Add ( i * i ) ; } for ( int i = 1 ; i * i * i * i <= n ; i ++ ) { quadruples . Add ( i * i * i * i ) ; } foreach ( int a in squares ) { foreach ( int b in quadruples ) { if ( allPrimes . Contains ( a + b ) ) intersetingPrimes . Add ( a + b ) ; } } return intersetingPrimes . Count ; } public static void Main ( String [ ] args ) { int N = 10 ; Console . Write ( countInterestingPrimes ( N ) ) ; } }