Count of primes in a given range that can be expressed as sum of perfect squares | Function to check if a prime number satisfies the condition to be expressed as sum of two perfect squares ; Function to check if a number is prime or not ; Corner cases ; Function to return the count of primes in the range which can be expressed as the sum of two squares ; If i is a prime ; If i can be expressed as the sum of two squares ; Return the count ; Driver code
def sumsquare ( p ) : NEW_LINE INDENT return ( p - 1 ) % 4 == 0 NEW_LINE DEDENT def isprime ( n ) : NEW_LINE INDENT if n <= 1 : NEW_LINE INDENT return False NEW_LINE DEDENT if n <= 3 : NEW_LINE INDENT return True NEW_LINE DEDENT if ( n % 2 == 0 ) or ( n % 3 == 0 ) : NEW_LINE INDENT return False NEW_LINE DEDENT i = 5 NEW_LINE while ( i * i <= n ) : NEW_LINE INDENT if ( ( n % i == 0 ) or ( n % ( i + 2 ) == 0 ) ) : NEW_LINE return False NEW_LINE i += 6 NEW_LINE DEDENT return True NEW_LINE DEDENT def countOfPrimes ( L , R ) : NEW_LINE INDENT count = 0 NEW_LINE for i in range ( L , R + 1 ) : NEW_LINE INDENT if ( isprime ( i ) ) : NEW_LINE if sumsquare ( i ) : NEW_LINE INDENT count += 1 NEW_LINE DEDENT DEDENT return count NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT L = 5 NEW_LINE R = 41 NEW_LINE print ( countOfPrimes ( L , R ) ) NEW_LINE DEDENT