Find two distinct prime numbers with given product | from math lib . import everything ; Function to generate all prime numbers less than n ; Initialize all entries of boolean array as true . A value in isPrime [ i ] will finally be false if i is Not a prime , else true bool isPrime [ n + 1 ] ; ; If isPrime [ p ] is not changed , then it is a prime ; Function to print a prime pair with given product ; Generating primes using Sieve ; Traversing all numbers to find first pair ; Driver code
from math import * NEW_LINE def SieveOfEratosthenes ( n , isPrime ) : NEW_LINE INDENT isPrime [ 0 ] , isPrime [ 1 ] = False , False NEW_LINE for i in range ( 2 , n + 1 ) : NEW_LINE INDENT isPrime [ i ] = True NEW_LINE DEDENT for p in range ( 2 , int ( sqrt ( n ) ) + 1 ) : NEW_LINE INDENT if isPrime [ p ] == True : NEW_LINE INDENT for i in range ( p * 2 , n + 1 , p ) : NEW_LINE INDENT isPrime [ i ] = False NEW_LINE DEDENT DEDENT DEDENT DEDENT def findPrimePair ( n ) : NEW_LINE INDENT flag = 0 NEW_LINE isPrime = [ False ] * ( n + 1 ) NEW_LINE SieveOfEratosthenes ( n , isPrime ) NEW_LINE for i in range ( 2 , n ) : NEW_LINE INDENT x = int ( n / i ) NEW_LINE if ( isPrime [ i ] & isPrime [ x ] and x != i and x * i == n ) : NEW_LINE INDENT print ( i , x ) NEW_LINE flag = 1 NEW_LINE break NEW_LINE DEDENT DEDENT if not flag : NEW_LINE INDENT print ( " No ▁ such ▁ pair ▁ found " ) NEW_LINE DEDENT DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT n = 39 ; NEW_LINE findPrimePair ( n ) NEW_LINE DEDENT