Maximum number of unique prime factors | Return maximum number of prime factors for any number in [ 1 , N ] ; Based on Sieve of Eratosthenes ; If p is prime ; We simply multiply first set of prime numbers while the product is smaller than N . ; Driver Code
< ? php function maxPrimefactorNum ( $ N ) { if ( $ N < 2 ) return 0 ; $ arr = array_fill ( 0 , ( $ N + 1 ) , true ) ; $ prod = 1 ; $ res = 0 ; for ( $ p = 2 ; $ p * $ p <= $ N ; $ p ++ ) { if ( $ arr [ $ p ] == true ) { for ( $ i = $ p * 2 ; $ i <= $ N ; $ i += $ p ) $ arr [ $ i ] = false ; $ prod *= $ p ; if ( $ prod > $ N ) return $ res ; $ res ++ ; } } return $ res ; } $ N = 500 ; echo maxPrimefactorNum ( $ N ) . " STRNEWLINE " ; ? >