Find two prime numbers with given sum | 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 ; Prints a prime pair with given sum ; Generating primes using Sieve ; Traversing all numbers to find first pair ; Driver Code
< ? php function SieveOfEratosthenes ( $ n , & $ isPrime ) { $ isPrime [ 0 ] = $ isPrime [ 1 ] = false ; for ( $ i = 2 ; $ i <= $ n ; $ i ++ ) $ isPrime [ $ i ] = true ; for ( $ p = 2 ; $ p * $ p <= $ n ; $ p ++ ) { if ( $ isPrime [ $ p ] == true ) { for ( $ i = $ p * $ p ; $ i <= $ n ; $ i += $ p ) $ isPrime [ $ i ] = false ; } } } function findPrimePair ( $ n ) { $ isPrime = array_fill ( 0 , $ n + 1 , NULL ) ; SieveOfEratosthenes ( $ n , $ isPrime ) ; for ( $ i = 0 ; $ i < $ n ; $ i ++ ) { if ( $ isPrime [ $ i ] && $ isPrime [ $ n - $ i ] ) { echo $ i . " ▁ " . ( $ n - $ i ) ; return ; } } } $ n = 74 ; findPrimePair ( $ n ) ; ? >