Queries to find whether a number has exactly four distinct factors or not | Initialize global variable according to given condition so that it can be accessible to all function ; Function to calculate all number having four distinct factors ; Create a boolean array " prime [ 0 . . n ] " and initialize all entries it as true . A value in prime [ i ] will finally be false if i is not a prime , else true . ; If prime [ p ] is not changed , then it is a prime ; Update all multiples of p ; Initialize prime [ ] array which will contains all the primes from 1 - N ; Iterate over all the prime numbers ; Mark cube root of prime numbers ; Mark product of prime numbers ; Driver Code
< ? php $ N = 1000001 ; $ fourDiv = array_fill ( 0 , $ N + 1 , false ) ; function fourDistinctFactors ( ) { global $ N ; global $ fourDiv ; $ primeAll = array_fill ( 0 , $ N + 1 , true ) ; for ( $ p = 2 ; $ p * $ p <= $ N ; $ p ++ ) { if ( $ primeAll [ $ p ] == true ) { for ( $ i = $ p * 2 ; $ i <= $ N ; $ i += $ p ) $ primeAll [ $ i ] = false ; } } $ prime ; $ x = 0 ; for ( $ p = 2 ; $ p <= $ N ; $ p ++ ) if ( $ primeAll [ $ p ] ) $ prime [ $ x ++ ] = $ p ; for ( $ i = 0 ; $ i < $ x ; ++ $ i ) { $ p = $ prime [ $ i ] ; if ( 1 * $ p * $ p * $ p <= $ N ) $ fourDiv [ $ p * $ p * $ p ] = true ; for ( $ j = $ i + 1 ; $ j < $ x ; ++ $ j ) { $ q = $ prime [ $ j ] ; if ( 1 * $ p * $ q > $ N ) break ; $ fourDiv [ $ p * $ q ] = true ; } } } fourDistinctFactors ( ) ; $ num = 10 ; if ( $ fourDiv [ $ num ] ) echo " Yes STRNEWLINE " ; else echo " No STRNEWLINE " ; $ num = 12 ; if ( $ fourDiv [ $ num ] ) echo " Yes STRNEWLINE " ; else echo " No STRNEWLINE " ; ? >