Найдите простые множители, включая их общее количество (Java)

Я пытался создать программу на Java для поиска LCM из «N» чисел. но прежде всего я застрял в поиске общих простых множителей числа, включая их вхождения. Например, (6=2x3) и (8=2x2x2). но на выходе я получаю «2» для (6) и только две «2» для (8). Где другие? Я даже проверяю, что целое число s простое.

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);
    }
   }
}

java prime-factoring
person Pradeep Vig    schedule 15.08.2015    source источник
comment
Причина в том, что когда s=2 и копия также становится 2, в этом случае она пропускает цикл, поэтому отображаются только две двойки. Попробуйте поставить ‹=copy в этом месте @kevin Souza   -  person Aditya Kiran    schedule 15.08.2015
comment
Есть лучший способ: LCM(a,b) = |a.b| / GCD(a,b) ... и вычислить НОД с помощью алгоритма Евклида.   -  person Stephen C    schedule 15.08.2015

Ответы (3)


arrow_upward
0
arrow_downward

Причина в том, что когда s=2 и копия также становится 2, в этом случае она пропускает цикл, поэтому отображаются только две двойки. Попробуйте поставить ‹=копировать в этом месте

person Aditya Kiran    schedule 15.08.2015
comment
И, кроме того, я бы изменил элемент управления factor(), чтобы он останавливался, когда переменная copy равна 1. - person itwasntme; 15.08.2015
comment
Кроме того, проверка простого числа не требуется. Если s составное, у копии не будет ни одного простого множителя из-за предшествующих делений. - person Patricia Shanahan; 15.08.2015

arrow_upward
0
arrow_downward

Я думаю, что один из лучших способов решить эту проблему — использовать рекурсию, поскольку вам постоянно приходится делить, чтобы найти все простые множители.

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;
    }
}

person Brice Djilo    schedule 16.08.2015
comment
Для рекурсии проверьте метод getPrimeFactors(int numero, ArrayList<Integer> primeFactors) в приведенном выше коде. - person Brice Djilo; 16.08.2015

arrow_upward
0
arrow_downward

Вот решение, которое быстрее с использованием двоичного разделения на алгоритме Евклида:

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));
}
person Charles    schedule 17.08.2015