Number which has the maximum number of distinct prime factors in the range M to N

Given two numbers M and N. The task is to print the number which has the maximum number of distinct prime factors of numbers in range M and N. If there exist multiple numbers, print the smallest one.

Examples:

Input: a=4, b=10
Output: 6
Number of distinct Prime Factors of 4 is 1
Number of distinct Prime Factors of 5 is 1
Number of distinct Prime Factors of 6 is 2
Number of distinct Prime Factors of 7 is 1
Number of distinct Prime Factors of 8 is 1
Number of distinct Prime Factors of 9 is 1
Number of distinct Prime Factors of 10 is 2

Input: a=100, b=150
Output: 102

Recommended: Please try your approach on {IDE} first, before moving on to the solution.

The approach is to use Sieve of Erathosthenes. Create a factorCount[] array to store the the number of distinct prime factors of a number. While marking the number as prime, increment the count of prime factors in its multiples. In the end, get the maximum number stored in the factorCount[] array which will be the answer.

Below is the implementation of the above approach:

C++

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

Java

 // Java program to print the // Number which has the maximum  // number of distinct prime  // factors of numbers in range // m to n import java.io.*;    class GFG {    // Function to return  // the maximum number static int maximumNumberDistinctPrimeRange(int m,                                             int n) {     // array to store the     // number of distinct primes     long factorCount[] = new long[n + 1];        // true if index 'i'     // is a prime     boolean prime[] = new boolean[n + 1];        // initializing the number     // of factors to 0 and     for (int i = 0; i <= n; i++)     {         factorCount[i] = 0;         prime[i] = true; // Used in Sieve     }        for (int i = 2; i <= n; i++)     {            // condition works only when          // 'i' is prime, hence for          // factors of all prime number,         // the prime status is changed to false         if (prime[i] == true)          {                // Number is prime             factorCount[i] = 1;                // number of factor of              // a prime number is 1             for (int j = i * 2; j <= n; j += i)              {                    // incrementing factorCount                  // all the factors of i                 factorCount[j]++;                    // and changing prime                 // status to false                 prime[j] = false;             }         }     }        // Initialize the max and num     int max = (int)factorCount[m];     int num = m;        // Gets the maximum number     for (int i = m; i <= n; i++)     {            // Gets the maximum number         if (factorCount[i] > max)         {             max = (int)factorCount[i];             num = i;         }     }     return num; }    // Driver code public static void main (String[] args)  { int m = 4, n = 6;    // Calling function System.out.println(maximumNumberDistinctPrimeRange(m, n)); } }    // This code is contributed by anuj_67.

Python 3

 # Python 3 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 def maximumNumberDistinctPrimeRange(m, n):        # array to store the number      # of distinct primes     factorCount =  * (n + 1)        # true if index 'i' is a prime     prime = [False] * (n + 1)        # initializing the number of     # factors to 0 and     for i in range(n + 1) :         factorCount[i] = 0         prime[i] = True # Used in Sieve        for i in range(2, n + 1) :            # condition works only when 'i'          # is prime, hence for factors of         # all prime number, the prime          # status is changed to false         if (prime[i] == True) :                # Number is prime             factorCount[i] = 1                # number of factor of a              # prime number is 1             for j in range(i * 2, n + 1, i) :                    # incrementing factorCount all                 # the factors of i                 factorCount[j] += 1                    # and changing prime status                 # to false                 prime[j] = False        # Initialize the max and num     max = factorCount[m]     num = m        # Gets the maximum number     for i in range(m, n + 1) :            # Gets the maximum number         if (factorCount[i] > max) :             max = factorCount[i]             num = i     return num    # Driver code if __name__ == "__main__":     m = 4     n = 6            # Calling function     print(maximumNumberDistinctPrimeRange(m, n))        # This code is contributed # by ChitraNayal

C#

 // C# program to print the // Number which has the maximum  // number of distinct prime  // factors of numbers in range // m to n using System;    class GFG {    // Function to return  // the maximum number static int maximumNumberDistinctPrimeRange(int m,                                             int n) {     // array to store the     // number of distinct primes     long []factorCount = new long[n + 1];        // true if index 'i'     // is a prime     bool []prime = new bool[n + 1];        // initializing the number     // of factors to 0 and     for (int i = 0; i <= n; i++)     {         factorCount[i] = 0;         prime[i] = true; // Used in Sieve     }        for (int i = 2; i <= n; i++)     {            // condition works only x         // when 'i' is prime, hence          // for factors of all prime          // number, the prime status         // is changed to false         if (prime[i] == true)          {                // Number is prime             factorCount[i] = 1;                // number of factor of              // a prime number is 1             for (int j = i * 2;                       j <= n; j += i)              {                    // incrementing factorCount                  // all the factors of i                 factorCount[j]++;                    // and changing prime                 // status to false                 prime[j] = false;             }         }     }        // Initialize the max and num     int max = (int)factorCount[m];     int num = m;        // Gets the maximum number     for (int i = m; i <= n; i++)     {            // Gets the maximum number         if (factorCount[i] > max)         {             max = (int)factorCount[i];             num = i;         }     }     return num; }    // Driver code public static void Main ()  { int m = 4, n = 6;    // Calling function Console.WriteLine(          maximumNumberDistinctPrimeRange(m, n)); } }    // This code is contributed // by anuj_67.

PHP

 \$max)          {             \$max = \$factorCount[\$i];             \$num = \$i;         }     }     return \$num; }    // Driver code \$m = 4; \$n = 6;    // Calling function echo maximumNumberDistinctPrimeRange(\$m, \$n);    // This code is contributed // by anuj_67. ?>

Output:

6