Find the number of ordered pairs such that a * p + b * q = N , where p and q are primes | Python3 program to find the number of ordered pairs such that a * p + b * q = N where p and q are primes ; Sieve of erastothenes to store the prime numbers and their frequency in form a * p + b * q ; Performing Sieve of Eratosthenes to find the prime numbers unto 10001 ; Loop to find the number of ordered pairs for every combination of the prime numbers ; Driver code ; Printing the number of ordered pairs for every query
from math import sqrt NEW_LINE size = 1000 NEW_LINE prime = [ 0 for i in range ( size ) ] NEW_LINE freq = [ 0 for i in range ( size ) ] NEW_LINE def sieve ( a , b ) : NEW_LINE INDENT prime [ 1 ] = 1 NEW_LINE for i in range ( 2 , int ( sqrt ( size ) ) + 1 , 1 ) : NEW_LINE INDENT if ( prime [ i ] == 0 ) : NEW_LINE INDENT for j in range ( i * 2 , size , i ) : NEW_LINE INDENT prime [ j ] = 1 NEW_LINE DEDENT DEDENT DEDENT for p in range ( 1 , size , 1 ) : NEW_LINE INDENT for q in range ( 1 , size , 1 ) : NEW_LINE INDENT if ( prime [ p ] == 0 and prime [ q ] == 0 and a * p + b * q < size ) : NEW_LINE INDENT freq [ a * p + b * q ] += 1 NEW_LINE DEDENT DEDENT DEDENT DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT queries = 2 NEW_LINE a = 1 NEW_LINE b = 2 NEW_LINE sieve ( a , b ) NEW_LINE arr = [ 15 , 25 ] NEW_LINE for i in range ( queries ) : NEW_LINE INDENT print ( freq [ arr [ i ] ] , end = " ▁ " ) NEW_LINE DEDENT DEDENT