Count of interesting primes upto 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
def SieveOfEratosthenes ( n , allPrimes ) : NEW_LINE INDENT prime = [ True ] * ( n + 1 ) NEW_LINE p = 2 NEW_LINE while p * p <= n : NEW_LINE INDENT if prime [ p ] == True : NEW_LINE INDENT for i in range ( p * p , n + 1 , p ) : NEW_LINE INDENT prime [ i ] = False NEW_LINE DEDENT DEDENT p += 1 NEW_LINE DEDENT for p in range ( 2 , n + 1 ) : NEW_LINE INDENT if prime [ p ] : NEW_LINE INDENT allPrimes . add ( p ) NEW_LINE DEDENT DEDENT DEDENT def countInterestingPrimes ( n ) : NEW_LINE INDENT allPrimes = set ( ) NEW_LINE SieveOfEratosthenes ( n , allPrimes ) NEW_LINE interestingPrimes = set ( ) NEW_LINE squares , quadruples = [ ] , [ ] NEW_LINE i = 1 NEW_LINE while i * i <= n : NEW_LINE INDENT squares . append ( i * i ) NEW_LINE i += 1 NEW_LINE DEDENT i = 1 NEW_LINE while i * i * i * i <= n : NEW_LINE INDENT quadruples . append ( i * i * i * i ) NEW_LINE i += 1 NEW_LINE DEDENT for a in squares : NEW_LINE INDENT for b in quadruples : NEW_LINE INDENT if a + b in allPrimes : NEW_LINE INDENT interestingPrimes . add ( a + b ) NEW_LINE DEDENT DEDENT DEDENT return len ( interestingPrimes ) NEW_LINE DEDENT N = 10 NEW_LINE print ( countInterestingPrimes ( N ) ) NEW_LINE