Find two distinct prime numbers with given product | 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 ; Update all multiples of p ; Function to print a prime pair with given product ; Generating primes using Sieve ; Traversing all numbers to find first pair ; Driver Code
< ? php function SieveOfEratosthenes ( $ n , & $ isPrime ) { $ isPrime [ 0 ] = false ; $ isPrime [ 1 ] = false ; for ( $ i = 2 ; $ i <= $ n ; $ i ++ ) $ isPrime [ $ i ] = true ; for ( $ p = 2 ; $ p * $ p <= $ n ; $ p ++ ) { if ( $ isPrime [ $ p ] ) { for ( $ i = $ p * 2 ; $ i <= $ n ; $ i += $ p ) $ isPrime [ $ i ] = false ; } } } function findPrimePair ( $ n ) { $ flag = 0 ; $ isPrime = array_fill ( 0 , ( $ n + 1 ) , false ) ; SieveOfEratosthenes ( $ n , $ isPrime ) ; for ( $ i = 2 ; $ i < $ n ; $ i ++ ) { $ x = ( int ) ( $ n / $ i ) ; if ( $ isPrime [ $ i ] && $ isPrime [ $ x ] and $ x != $ i and $ x * $ i == $ n ) { echo $ i . " ▁ " . $ x ; $ flag = 1 ; return ; } } if ( ! $ flag ) echo " No ▁ such ▁ pair ▁ found " ; } $ n = 39 ; findPrimePair ( $ n ) ; ? >