Java: Find the number which has the maximum number of distinct prime factors in a given range

Last update on March 11 2025 11:06:01 (UTC/GMT +8 hours)

Max Distinct Prime Factors in Range

Write a Java program to find the number with the maximum number of distinct prime factors in a given range.

Sample Solution:

Java Code:

import java.util.*;

public class solution {
    static int max_distinct_primes(int r1, int r2) 
{ 
    long factor_count[] = new long[r2 + 1]; 
    boolean prime_num[] = new boolean[r2 + 1]; 
    for (int i = 0; i <= r2; i++) 
    { 
        factor_count[i] = 0; 
        prime_num[i] = true;
    } 
  
    for (int i = 2; i <= r2; i++) 
    { 
        if (prime_num[i] == true)  
        { 
  
           factor_count[i] = 1; 
           for (int j = i * 2; j <= r2; j += i)  
            { 
                factor_count[j]++; 
                prime_num[j] = false; 
            } 
        } 
    } 
 
    int max_num = (int)factor_count[r1]; 
    int num = r1; 
  
    for (int i = r1; i <= r2; i++) 
      {   
        if (factor_count[i] > max_num) 
        { 
            max_num = (int)factor_count[i]; 
            num = i; 
        } 
    } 
    return num; 
} 
  
   public static void main(String[] args) {
       Scanner scan = new Scanner(System.in);
       System.out.print("Input first integer: ");
       int num1 = scan.nextInt();
       System.out.print("Input second integer: ");
       int num2 = scan.nextInt();
       scan.close(); 
	   if (num1>0 && num2>0 && num2>num1)
	   {
          System.out.println("Maximum number of distinct prime factors of the said range: "+max_distinct_primes(num1, num2));		
	   }
		}
}

Sample Output:

Input first integer:  5
Input second integer:  25
Maximum number of distinct prime factors of the said range: 6

Flowchart:

For more Practice: Solve these Related Problems:

• Write a Java program to find the number within a range that has the maximum number of distinct prime factors using the Sieve method.
• Write a Java program to compute distinct prime factors for each number in a range and then determine the maximum count.
• Write a Java program to optimize the search for maximum distinct prime factors by caching factors for each number.
• Write a Java program to compare each number in a range and output the one with the highest number of unique prime factors along with its factors.

Java Code Editor:

Contribute your code and comments through Disqus.

Previous: Write a Java program to print all primes smaller than or equal to any given number.
Next: Write a Java program to find next smallest palindrome.