Count of interesting primes upto N | Python3 program to find the number of interesting primes up to N ; Function to check if a number is prime or not ; If n is divisible by any number between 2 and sqrt ( n ) , it is not prime ; Function to check if a number is perfect square or not ; Find floating povalue of square root of x . ; If square root is an integer ; Function to find the number of interesting primes less than equal to N . ; Check whether the number is prime or not ; Iterate for values of b ; Check condition for a ; Return the required answer ; Driver code
import math NEW_LINE def isPrime ( n ) : NEW_LINE INDENT flag = 1 NEW_LINE i = 2 NEW_LINE while ( i * i <= n ) : NEW_LINE INDENT if ( n % i == 0 ) : NEW_LINE INDENT flag = 0 NEW_LINE break NEW_LINE DEDENT i += 1 NEW_LINE DEDENT return ( True if flag == 1 else False ) NEW_LINE DEDENT def isPerfectSquare ( x ) : NEW_LINE INDENT sr = math . sqrt ( x ) NEW_LINE return ( ( sr - math . floor ( sr ) ) == 0 ) NEW_LINE DEDENT def countInterestingPrimes ( n ) : NEW_LINE INDENT answer = 0 NEW_LINE for i in range ( 2 , n ) : NEW_LINE INDENT if ( isPrime ( i ) ) : NEW_LINE INDENT j = 1 NEW_LINE while ( j * j * j * j <= i ) : NEW_LINE INDENT if ( isPerfectSquare ( i - j * j * j * j ) ) : NEW_LINE INDENT answer += 1 NEW_LINE break NEW_LINE DEDENT j += 1 NEW_LINE DEDENT DEDENT DEDENT return answer NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT N = 10 NEW_LINE print ( countInterestingPrimes ( N ) ) NEW_LINE DEDENT