Number which has the maximum number of distinct prime factors in the range M to N | C ++ program to print the Number which has the maximum number of distinct prime factors of numbers in range m to n ; Function to return the maximum number ; array to store the number of distinct primes ; true if index ' i ' is a prime ; initializing the number of factors to 0 and ; Used in Sieve ; condition works only when ' i ' is prime , hence for factors of all prime number , the prime status is changed to false ; Number is prime ; number of factor of a prime number is 1 ; incrementing factorCount all the factors of i ; and changing prime status to false ; Initialize the max and num ; Gets the maximum number ; Gets the maximum number ; Driver code ; Calling function
#include <bits/stdc++.h> NEW_LINE using namespace std ; int maximumNumberDistinctPrimeRange ( int m , int n ) { long long factorCount [ n + 1 ] ; bool prime [ n + 1 ] ; for ( int i = 0 ; i <= n ; i ++ ) { factorCount [ i ] = 0 ; prime [ i ] = true ; } for ( int i = 2 ; i <= n ; i ++ ) { if ( prime [ i ] == true ) { factorCount [ i ] = 1 ; for ( int j = i * 2 ; j <= n ; j += i ) { factorCount [ j ] ++ ; prime [ j ] = false ; } } } int max = factorCount [ m ] ; int num = m ; for ( int i = m ; i <= n ; i ++ ) { if ( factorCount [ i ] > max ) { max = factorCount [ i ] ; num = i ; } } return num ; } int main ( ) { int m = 4 , n = 6 ; cout << maximumNumberDistinctPrimeRange ( m , n ) ; return 0 ; }