Получить простые множители заданного числа с помощью Java

Я пытаюсь получить простые множители заданного числа с помощью java. Мне удалось написать следующий код. Он возвращает 2,5,10 для простых множителей 100, в то время как 10 не является простым числом, а также возвращает 2, 4,11 для простых делителей 88, если 4 не является простым числом. Может ли кто-нибудь объяснить, в чем причина и как ее исправить?

import java.util.ArrayList;
import java.util.Random;

public class PrimeFactors {
public static void main(String[] args) {
    Random randomGenarator = new Random();
    int number = randomGenarator.nextInt(150);
    System.out.println("Prime factors of :" + number);
    findPrimeFactors(number);

}

private static void findPrimeFactors(int i) {
    ArrayList<Integer> list = new ArrayList<Integer>();
    for (int n = 2; n <= i; n++) {
        if (i % n == 0) {
            list.add(n);
            i /= n;

        }
    }
    for (int n : list) {
        System.out.println(n);
    }

  }
}

java factors primes
person Kaveen    schedule 17.06.2015    source источник

Ответы (2)


arrow_upward
1
arrow_downward

Вы не тестируете несколько одинаковых факторов в исходном числе. Например. при тестировании 88 вы найдете 2, но упустите другие 2. (Число теперь 44.) Затем вы переходите к 3 и не находите его. Затем вы найдете 4, потому что 4 является фактором 44.

Вы должны продолжать тестировать фактор, пока не перестанете его находить. Замените if на while:

while (i % n == 0) {
    list.add(n);
    i /= n;
}

Таким образом, вы найдете все 2 в множителе прежде всего. Затем, когда вы доберетесь до других составных чисел, таких как 4, для проверки, вы их не найдете.

person rgettman    schedule 17.06.2015
comment
Спасибо за объяснение. Это действительно помогло мне понять проблему. - person Kaveen; 17.06.2015

arrow_upward
0
arrow_downward

Ты делаешь это неправильно . вам нужно удалить все делители простого числа, прежде чем двигаться дальше.

например (псевдокод)

 if i=100 ,
 continue dividing it by 2 until it is non-divisible 
 i=100/2 =50 , 
 then i=50/2 =25 then stop,
 then look for next prime.

Надеюсь, поможет.

person akash300    schedule 17.06.2015