Факторизация простых чисел с помощью Java и нахождение верхней границы

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

Цель: найти простые факторизации числа n. Затем объедините простые множители в одно число x. Затем возьмите это число x и разделите на n. Если x%n = 0, выведите True. Если x%n != 0, выведите false. (т. е. если n = 100, простые множители равны 2,2,5,5. Превратите в 2255, затем возьмите 2255/100. 2255%100 != 0, выведите False. )

То, что у меня есть сейчас, правильно распечатывает простые множители для некоторых чисел, но когда я пытаюсь использовать другое простое число, программа завершает работу. Кроме того, если я использую число, например 123, будет напечатано только 3, а не 3 и 41. Есть ли у вас какие-либо предложения?

Если возможно, в идеале я хотел бы запустить это для чисел j = 2 через любую верхнюю границу, которую я установил, назвать верхнюю границу U, и если любое значение для j = 2 через U дает истинный результат (сверху). Тогда я хотел бы напечатать это значение j.

import acm.program.*;
import acm.util.*;
import java.util.Scanner;
import java.util.Arrays.*;
// -------------------------------------------------------------------------

public class FactorsLoop extends ConsoleProgram
{
//~ Instance/static variables .............................................
private RandomGenerator rgen = RandomGenerator.getInstance();
//~ Constructor ...........................................................
// ----------------------------------------------------------
/**
 * Creates a new ForLoops object.
 */
public void run()
{
    // 


    int n1 = 10000;
    int n2 =(n1);

    double U = 10000;
    StringBuilder factors = new StringBuilder();
    for (int j = 2; j < U; j++) {

        for (int i = 2; i*i <= n1; i++) {
            // if i is a factor of N, repeatedly divide it out
            while (n1% i == 0) {

                n1 = n1 / i;


                factors.append(Integer.toString(i));

            }

        }

    }

    double newNumber = Integer.parseInt(factors.toString());

    double x = (newNumber / n2);

    print(x);

    if ( newNumber % n2 == 0 ){
        println(n2);    
    }
}

}


java primes prime-factoring
person L Brunot    schedule 26.03.2016    source источник
comment
Возможный дубликат наибольшего простого множителя числа в Java   -  person pczeus    schedule 26.03.2016

Ответы (1)


arrow_upward
0
arrow_downward

Ваш код правильно добавляет все те простые числа к factors, которые он делит. Однако он также должен добавить n1 после цикла, если он окажется != 1 (что произойдет именно тогда, когда степень наибольшего множителя равна 1).

Причина заключается в оптимизации вашего кода, в соответствии с которой внутренний цикл завершается, когда текущий коэффициент превышает sqrt(n1) (условие i*i <= n1 в заголовке цикла for). Это правильная оптимизация, но, как и многие другие оптимизации, она делает логику более сложной и подверженной ошибкам...

Примечание: внешний цикл, который повторяет j, кажется, вообще не имеет смысла; это приведет только к многократному добавлению небольших факторов. Приведите внутренний цикл в рабочую форму, выделите его в отдельную функцию (каламбур), а затем используйте его для реализации ранжированного теста, который ищет первый результат, удовлетворяющий некоторому критерию.

Например, функция, которая возвращает конкатенированные факторы, может выглядеть так:

public string concatenated_factors (int n)
{
    StringBuilder result = new StringBuilder();

    for (int i = 2; i * i <= n; ++i)
        for ( ; n % i == 0; n /= i)
            result.append(Integer.toString(i));

    if (n != 1)
        result.append(Integer.toString(n));

    return result.toString();
}

Примечание. Я не знаком с Java, поэтому некоторые подробности здесь могут быть немного нечеткими.

person DarthGizka    schedule 26.03.2016
comment
Куда бы я добавил n1 после цикла? после цикла while или после цикла for? И вы говорите, если i*i != 1 или если n1%i != 1? Не могли бы вы показать мне, просто скопировав часть моего кода, о которой вы говорите? Кстати, спасибо за ответ. - person L Brunot; 27.03.2016
comment
@L Брюно: готово. P.S.: пожалуйста, не забудьте принять мой ответ, если вы обнаружите, что он достаточно отвечает на ваш вопрос. И, пожалуйста, загляните на страницу тура, чтобы получить общее представление и понять, почему голосование по вопросам, ответам и комментариям важно. - person DarthGizka; 27.03.2016