找到主要因素，包括它們的總髮生次數（Java）

Question

我試圖構建一個用於查找'N'數字LCM的Java程序。但首先我堅持要找出一個數字的總素數，包括它們的出現次數。例如（6 = 2×3）和（8 = 2×2×2）。但是我得到的輸出是（6）的'2'和（8）的兩個'2'。對方在哪裏？我甚至會檢查整數'是否爲素數。

package lcm; 

import java.util.ArrayList; 
import java.util.Scanner; 

public class LCM { 
    public static boolean isPrime(int numero){ 
    for (int i = 2; i <= Math.sqrt(numero); i++) { 
     if (numero % i == 0) { 
      return false; 
     } 
    } 
    return true; 
    } 
    public static void factor(int x){  
     int s; 
     int copy = x; 
     ArrayList<Integer> al = new ArrayList<>(); 
     for(s=2;s<copy;s++){ 
      if(copy%s==0){ 
       if (isPrime(s)){ 
        al.add(s); 
        copy/=s; 
        //used for repetition 
        s--; 
       } 
      } 
     } 
     for(int p : al){ 
     System.out.println(p);  
     } 
    } 
public static void main(String[] args) { 
    // TODO code application logic here 
    int j,k; 
    int temp=0; 
    System.out.println("Enter no. of numbers"); 
    Scanner cin = new Scanner(System.in); 
    int i = cin.nextInt(); 
    int []a = new int[i]; 
    int []b=new int[100]; 
    System.out.println("Enter numbers one by one"); 

    for(j=0;j<a.length;j++){ 
     a[j] = cin.nextInt(); 
    } 
    for(j=0;j<a.length;j++){ 
     temp=a[j]; 
     factor(temp); 
    } 
    } 
} 

Answer 1

原因是當s = 2並且複製也變爲2時，它會跳過循環，因此只顯示兩個2。嘗試把< =複製在那個地方

Answer 2

我認爲解決這個問題最好的方法之一是使用遞歸，因爲你不斷地分裂，以找到所有的主要因素。

package leastcommonmultiple; 

import java.util.ArrayList; 
import java.util.Scanner; 

public class Runner { 

    private static LeastCommonMultiple lcm; 

    /** 
    * @param args the command line arguments 
    */ 
    public static void main(String[] args) { 

     System.out.println("Enter numbers and separate them with a comma: "); 
     Scanner cin = new Scanner(System.in); 
     String[] inputs; 
     String lineInput; 
     try { 
      lineInput = cin.nextLine(); 
      while (lineInput.isEmpty()) { 
       System.out.println("Enter at least 2 numbers separated by a comma "); 
       lineInput = cin.nextLine(); 
      } 
      inputs = lineInput.split(","); 
      int length = inputs.length; 
      int[] numbers = new int[length]; 
      int temp = 0; 
      for (int i = 0; i < length; i++) { 
       if (inputs[i] != null && !inputs[i].isEmpty()) { 
        if ((temp = Math.abs(Integer.valueOf(inputs[i].trim()))) == 0) { 
         throw new IllegalArgumentException("No number should be 0"); 
        } 
        numbers[i] = temp; 
       } 
      } 
      ArrayList<Integer> list = new ArrayList<>(); 
      lcm = new LeastCommonMultiple(); 
      System.out.println("The Least Common Multiple is: " + lcm.getLeastCommonMultipleOfListOfNumbers(numbers)); 
     } catch (Exception e) { 
      System.err.println(e.getMessage()); 
     } 
    } 
} 


package leastcommonmultiple; 

import java.util.ArrayList; 

public class LeastCommonMultiple { 

    public LeastCommonMultiple() { 
    } 

    /** 
    * @param numbers array of numbers whose LCM should be found. 
    * @assure  numbers.length > 1 
    * @return LCM of numbers contained in numbers array 
    */ 
    public int getLeastCommonMultipleOfListOfNumbers(int[] numbers) throws IllegalArgumentException { 
     int leastCommonMultiple; 
     int length = numbers.length; 
     if (length <= 1) { 
      throw new IllegalArgumentException("Please enter at least 2 numbers separated by a comma."); 
     } else { 
      leastCommonMultiple = getLeastCommonMultipleOfTwoNumbers(numbers[0], numbers[length-1]); 
      length = length-1; 
      for (int i=1; i<length; i++) { 
       leastCommonMultiple = getLeastCommonMultipleOfTwoNumbers(leastCommonMultiple, numbers[i]); 
      } 
     } 
     return leastCommonMultiple; 
    } 

    private int getLeastCommonMultipleOfTwoNumbers(int number1, int number2) { 
     int leastCommonMultiple = 0; 
     int maxOfTheTwoNumbers = Math.max(number1, number2); 
     int minOfTheTwoNumbers = Math.min(number1, number2); 
     int quotient = 0; 
     if (number1 % number2 == 0 || number2 % number1 == 0) { 
      leastCommonMultiple = maxOfTheTwoNumbers; 
     } else { 
      ArrayList<Integer> primeFactors = getPrimeFactors(minOfTheTwoNumbers, new ArrayList<>()); 
      for (int primeFactor : primeFactors) { 
       if (maxOfTheTwoNumbers % primeFactor == 0) { 
        maxOfTheTwoNumbers = (maxOfTheTwoNumbers/primeFactor); 
       } 
       leastCommonMultiple = minOfTheTwoNumbers * maxOfTheTwoNumbers; 
      } 
     } 
     return leastCommonMultiple; 
    } 


    // recursive methods that finds all the prime factors for a given number 
    /** 
    * @param numero positive number whose prime factors has to be found 
    * @param primeFactors an empty ArrayList where the prime factors will be 
    * stored 
    * @return the ArrayList containing the found prime factors 
    */ 
    private static ArrayList<Integer> getPrimeFactors(int numero, ArrayList<Integer> primeFactors) { 
     int sqrt = (int) Math.sqrt(numero); 
     int quotient; 
     if (isPrime(numero)) { 
      primeFactors.add(numero); 
     } else { 
      if (numero % sqrt == 0) { 
       quotient = numero/sqrt; 
       if (isPrime(sqrt)) { 
        primeFactors.add(sqrt); 
       } else { 
        primeFactors = getPrimeFactors(sqrt, primeFactors); 
       } 
      } else { 
       quotient = numero/(sqrt - 1); 
       if (isPrime(sqrt - 1)) { 
        primeFactors.add(sqrt - 1); 
       } else { 
        primeFactors = getPrimeFactors((sqrt - 1), primeFactors); 
       } 
      } 
      if (!isPrime(quotient)) { 
       primeFactors = getPrimeFactors(quotient, primeFactors); 
      } else { 
       primeFactors.add(quotient); 
      } 
     } 
     return primeFactors; 
    } 


    // Make sure a number is prime 
    public static boolean isPrime(int numero) { 
     int length = (int) Math.sqrt(numero); 
     for (int i = 2; i <= length; i++) { 
      if (numero % i == 0) { 
       return false; 
      } 
     } 
     return true; 
    } 
} 

Answer 3

這裏的一個解決方案，它是更快的通過使用關於歐幾里德算法二進制分裂：

private static int gcd(int a, int b) { 
    if (a == 0) return b; 
    if (b == 0) return a; 
    return gcd(b, a%b); 
} 

private static int lcm(int a, int b) { 
    return a/gcd(a, b) * b; 
} 

public static int LCM(int[] numbers) { 
    int len = numbers.length; 
    if (len == 2) return lcm(numbers[0], numbers[1]); 
    if (len == 1) return numbers[0]; 
    if (len == 0) return 1; 
    int[] left = Arrays.copyOfRange(numbers, 0, len/2); 
    int[] right = Arrays.copyOfRange(numbers, len/2+1, len); 
    return lcm(LCM(left), LCM(right)); 
}