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
def maxPrimefactorNum ( N ) : NEW_LINE INDENT if ( N < 2 ) : NEW_LINE INDENT return 0 ; NEW_LINE DEDENT arr = [ True ] * ( N + 1 ) ; NEW_LINE prod = 1 ; NEW_LINE res = 0 ; NEW_LINE p = 2 ; NEW_LINE while ( p * p <= N ) : NEW_LINE INDENT if ( arr [ p ] == True ) : NEW_LINE INDENT for i in range ( p * 2 , N + 1 , p ) : NEW_LINE INDENT arr [ i ] = False ; NEW_LINE DEDENT prod *= p ; NEW_LINE if ( prod > N ) : NEW_LINE INDENT return res ; NEW_LINE DEDENT res += 1 ; NEW_LINE DEDENT p += 1 ; NEW_LINE DEDENT return res ; NEW_LINE DEDENT N = 500 ; NEW_LINE print ( maxPrimefactorNum ( N ) ) ; NEW_LINE