Maximum number of unique prime factors | C ++ program to find maximum number of prime factors in first N natural numbers ; 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 . ; Driven Program
#include <bits/stdc++.h> NEW_LINE using namespace std ; int maxPrimefactorNum ( int N ) { if ( N < 2 ) return 0 ; bool arr [ N + 1 ] ; memset ( arr , true , sizeof ( arr ) ) ; int prod = 1 , res = 0 ; for ( int p = 2 ; p * p <= N ; p ++ ) { if ( arr [ p ] == true ) { for ( int i = p * 2 ; i <= N ; i += p ) arr [ i ] = false ; prod *= p ; if ( prod > N ) return res ; res ++ ; } } return res ; } int main ( ) { int N = 500 ; cout << maxPrimefactorNum ( N ) << endl ; return 0 ; }