Найти простое число длиной не менее 100 цифр, содержащее 273042282802155991

Question

Я новичок в Java, и одно из моих заданий в классе - найти простое число длиной не менее 100 цифр, содержащее числа 273042282802155991.

Пока у меня это есть, но когда я компилирую и запускаю его, кажется, что он находится в непрерывном цикле.

Я не уверен, что сделал что-то не так.

public static void main(String[] args) {
    BigInteger y = BigInteger.valueOf(304877713615599127L);
    System.out.println(RandomPrime(y));
}

public static BigInteger RandomPrime(BigInteger x)
{
    BigInteger i;

    for (i = BigInteger.valueOf(2); i.compareTo(x)<0; i.add(i)) {
        if ((x.remainder(i).equals(BigInteger.ZERO))) {
            x.divide(i).equals(x);
            i.subtract(i);
        }
    }
    return i;
}

Answer 1

Так как это домашнее задание ...

1. В BigInteger есть метод, проверяющий на простоту. Это намного быстрее, чем пытаться разложить число на множители. (Если вы выберете подход, предусматривающий попытку факторизации 100-значных чисел, вы потерпите неудачу. Факторизация считается NP-полной проблемой. Конечно, не существует известного решения за полиномиальное время .)

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

3. Подход генерации «случайных» простых чисел и последующего тестирования, содержат ли они эти цифры, невозможен. (Некоторые простые математики средней школы говорят вам, что вероятность того, что случайно сгенерированное 100-значное число содержит заданную последовательность из 18 цифр, составляет ... 82/10 ¹⁸ . И вы еще не проверяли на простоту. ..

4. Но есть еще один способ сделать это ... подумать об этом!

Начинайте писать код только после того, как в своей голове вы поймете, как будет работать ваш алгоритм, и сделаете мысленные оценки, чтобы подтвердить, что он даст ответ в разумные сроки.

---

_{Когда я говорю «неосуществимое», я имею в виду «неосуществимое» для вас. Учитывая достаточно большое количество компьютеров, достаточное количество времени и некоторую мощную математику, может быть в состоянии сделать некоторые из этих вещей. Таким образом, технически они могут быть вычислительно осуществимыми. Но они не осуществимы как домашнее задание. Я уверен, что цель этого упражнения - заставить вас подумать о том, как сделать это умным способом ...}

Answer 2

Один совет в том, что эти операторы ничего не делают:

x.divide(i).equals(x);
i.subtract(i);

То же самое с частью вашего цикла for:

i.add(i)

Они сами не изменяют экземпляры, новозвращать новые значения - значения, которые вы не можете проверить и сделать что-либо.BigIntegers являются «неизменными».Они не могут быть изменены - но с ними можно работать и возвращать новые значения.

Если вы действительно хотите сделать что-то подобное, вам нужно будет сделать:

i = i.add(i);

Такжес чего бы вы вычли i из i?Разве вы не ожидаете, что это будет 0?

Answer 3

Вам необходимо реализовать / использовать алгоритм Миллера-Рабина

Справочник по прикладной криптографии

глава 4.24 http://www.cacr.math.uwaterloo.ca/hac/about/chap4.pdf