Tutorialspoint.dev

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



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 <bits/stdc++.h>
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 = [0] * (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

<?php
// PHP 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
function maximumNumberDistinctPrimeRange($m, $n)
{
    // array to store the number
    // of distinct primes
    $factorCount = array();
  
    // true if index 
    // 'i' is a prime
    $prime = array();
  
    // initializing the number
    // of factors to 0 and
    for ($i = 0; $i <= $n; $i++) 
    {
        $factorCount[$i] = 0;
        $prime[$i] = true; // Used in Sieve
    }
  
    for ($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 ($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
    $max = $factorCount[$m];
    $num = $m;
  
    // Gets the maximum number
    for ($i = $m; $i <= $n; $i++) 
    {
  
        // Gets the maximum number
        if ($factorCount[$i] > $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


This article is attributed to GeeksforGeeks.org

leave a comment

code

0 Comments

load comments

Subscribe to Our Newsletter