Конструктор Прайм Фактор

Я делаю два класса, класс построения и основной метод, где я читаю число из пользовательского ввода и выплевываю простые факторизации числа, код с Java.

Например:
Введите число: 150
5
5
3
2

Однако для моей программы я получаю весь список факторов.

Пример:
Введите число: 150
150
75
50
25
5
3
1

Как бы я изменил это, чтобы получить простые множители?

Основной метод:

import java.util.*;

public class FactorPrinter
{
    public static void main(String[] args)
    {
        Scanner scan = new Scanner(System.in);
        System.out.print("Enter a integer: ");
        String input1 = scan.nextLine();
        int input = Integer.parseInt(input1);
        FactorGenerator factor = new FactorGenerator(input);
        System.out.print(factor.getNextFactor());

        while (!factor.hasMoreFactors())
        {
            System.out.print(factor.getNextFactor());
        }
     }  
}

Вот мой класс:

public class FactorGenerator 
{
    private int num;
    private int nextFactor;

    public FactorGenerator(int n)
    {
        num = nextFactor = n;
    }

    public int getNextFactor()
    {
        int i = nextFactor - 1 ;

        while ((num % i) != 0)
        {
            i--;
        }

        nextFactor = i;
        return i;
    }

    public boolean hasMoreFactors()
    {
        if (nextFactor == 1)
        {
            return false;
        }
        else
        {
            return true;
        }
    }
}

java factorization
person user2197917    schedule 22.03.2013    source источник
comment
если мне не изменяет память, все, что вам нужно сделать, чтобы получить простые множители, — это многократно делить на наименьшее число, которое вы можете, начиная с 2, а затем работать оттуда. например, 14 делится на 2, поэтому 2 является простым множителем, 7 не делится на 2, поэтому вы больше не можете делить, попробуйте 3, затем 4,5,6, затем 7. бум, простые множители 2 и 7.   -  person mpen    schedule 22.03.2013
comment
@EJP: Это действительно так. Например, при разложении на множители 12 4 — это множитель, верно? 4 никогда не появится в моем алгоритме, потому что 4 делится на 2, которые вы уже разделили. Требуется некоторое время, чтобы обернуть голову, но оказывается, что это только простые числа;)   -  person mpen    schedule 22.03.2013

Ответы (3)


arrow_upward
2
arrow_downward

Исправленная версия удаленного ответа @Bohemian:

for (int i = 2; input > 1 && i <= input; i++)
{
    if (input % i == 0)
    {
        System.out.print(i+" ");
        do
        {
            input /= i;
        } while (input % i == 0);
    }
}

Есть гораздо более быстрые алгоритмы, например. Алгоритм Кнута The Art of Computer Programming, Vol I, #4.5.4 C, полученный от Fermat, но обратите внимание, что на его веб-сайте есть важное исправление. Он дает хорошее тестовое значение как 8616460799L, так как оно имеет два довольно больших простых множителя.

person user207421    schedule 22.03.2013
comment
@SunilRk Ваш код также не выводит простые числа: это также O (N). Рекомендовать вообще нечего, извините. - person user207421; 22.03.2013
comment
Спасибо за помощь, я заставил код работать, но когда код повторяет простой множитель, он не печатается. - person user2197917; 22.03.2013
comment
Первичный фактор есть первичный фактор. Это не должно быть напечатано дважды. - person user207421; 22.03.2013
comment
Мне объяснили, что простые множители — это комбинации, которые непосредственно составляют целое число, поэтому 150 = 5 x 5 x 3 x 2. Однако я согласен с вашим утверждением. - person user2197917; 22.03.2013
comment
@EJP: Вы понимаете, что решение, которое вы разместили здесь, точно такое же, как то, что я описал в своем комментарии? Зачем вы публикуете это, если это не избавляет от неосновных факторов? - person mpen; 22.03.2013
comment
@Mark Спасибо: кажется, я неправильно понял ваш комментарий. Я пропустил слово "неоднократно". - person user207421; 23.03.2013
comment
@user2197917 user2197917 Если вы хотите, чтобы факторы повторялись, просто переместите печать внутрь цикла do/while. - person user207421; 23.03.2013

arrow_upward
0
arrow_downward

Вы можете добавить метод, чтобы проверить, является ли возвращаемый фактор простым или нет: попробуйте что-то вроде этого:

public bool isPrime(int number) {
    int i;
    for (i=2; i*i<=number; i++) {
        if (number % i == 0) return false;
    }
    return true;
}

И вы можете использовать это как:

 public class FactorPrinter
{
    public static void main(String[] args)
    {
        //your initial code

        while (!factor.hasMoreFactors())
        {
            int nextFactor= factor.getNextFactor()

            if(isPrime(nextFactor))
           {
            System.out.print();
           }
        }
     }  
}
person Priyanka.Patil    schedule 22.03.2013

arrow_upward
0
arrow_downward

Следующий метод будет печатать простые множители для заданного числа. Он также содержит несколько оптимизаций.

public static void primeFactors(int n) {
    if (n <= 1) {
        return;
    }
    while (n % 2 == 0) {
        System.out.println(2);
        n = n / 2;
    }
    while (n % 3 == 0) {
        System.out.println(3);
        n = n / 3;
    }
    for (int i = 5; i * i <= n; i += 6) {
        while (n % i == 0) {
            System.out.println(i);
            n = n / i;
        }
        while (n % (i + 2) == 0) {
            System.out.println(i + 2);
            n = n / (i + 2);
        }
    }
    if (n > 3) {
        System.out.println(n);
    }
}
person Chamal Perera    schedule 21.11.2020