Простые числа

В джаве класс BigDecimal. Но оперативы может тупо не хватить.

В питоне можно регулировать размерность аналогичного стандартного обьекта Decimal, у него есть атрибуты getcontext().prec,
getcontext().Emax, размерность можно увеличивать до бесконечности
Но питон при этом становится чрезвычайно задумчивым

Четвертая проверка - возводим двойку в степень R и проверяем на взаимную простоту с искомым числом N

Мне одному кажется что в этом пункте что-то не так?

Ты смотрел сколько памяти было съедено?

Мне одному кажется что в этом пункте что-то не так?

Не только тебе
Я когда написал тестовую программу на питоне, то понял, что третья и четвертая проверки начиная где-то с 5-й итерации практически перестают работать на обычной персоналке в силу неподьемности
Я оставил первые две проверки - получаются как бы простые числа

Ты смотрел сколько памяти было съедено?

А дело не в памяти
Там самым узким местом является проц
На работе у меня 8 гигов оперативки, дома 2, я пробовал свою тестовую программу и там, и там, ведет она себя практически одинаково и там, и там, т.е. после где-то 7-й итерации практически «засыпает»

Я даже не про память, которой понятно что не хватит. Возводить двойку в степень с тысячью десятичных знаков? Серьезно? На это уйдет примерно 10⁹⁹⁹ байт памяти. Это какбе сильно больше количества атомов в наблюдаемой вселенной.

Но меня напрягло другое: кому в голове пришла мысль сравнивать на взаимною простоту два числа, одно из которых заведомо является степенью двойки, а второе заведомо нечетно?

Но меня напрягло другое: кому в голове пришла мысль сравнивать на взаимною простоту два числа, одно из которых заведомо является степенью двойки, а второе заведомо нечетно?

там первое число - степень двойки минус один - т.е. также нечетное число

там первое число - степень двойки минус один - т.е. также нечетное число

не вижу

Четвертая проверка - возводим двойку в степень R и проверяем на взаимную простоту с искомым числом N

Я сейчас сделал два прогона своей тестовой программки на питоне
В первом случае я получил такие результаты: начал я с простого числа
9999991
1 итерация - 15 разрядов: 345078509429063
2 итерация - 30 разрядов: 218184211721730655148630816873
3 итерация - 60 разрядов: 115606163781003438179279231222831172612076571103016960737637
4 итерация - 119 разрядов: 39247129633132625073600902750031217385758579848302627869614195214695124307814770397329816974917312383244400813722289441

Есть такой сайт по проверке простых чисел - http://www.numberempire.com/primenumbers.php

Он говорит, что последнее число - простое :-)

Возводить двойку в степень с тысячью десятичных знаков? Серьезно? На это уйдет примерно 10⁹⁹⁹ байт памяти.

Бит, а не байт. Но они все нули.

Если тебе нужно абы какое простое число, то числа Мерсенна известны давным-давно. Если число должно быть криптостойким (с хорошим распылением), то это отдельная большая пестня.

Ещё Евклид показал, что при наличии некоего простого списка (a,b) всегда будет существовать простое число a*b+1.

Но нужно правильно определять список - ибо 2*7+1=15=5*3. Числа (a,b) должны быть наибольшими в особом смысле.

И незачем морочить голову.

Есть такой сайт по проверке простых чисел - http://www.numberempire.com/primenumbers.php

О, я придумал алгоритм быстрее и проще!

1. Берём число N+1

2. Первая проверка. Проверяем число на этом сайте.

3. Готово!

5 Третья проверка - возводим двойку в степень N-1, результат делим на N

Мне кажется, или в проверке ещё должно что-то проверяться?

Возводить достаточно по модулю N, так что памяти много не надо.

можно просто N быстрее работает.

по теме есть библиотека https://gmplib.org/ для работы с большими числами

Cпасибо, посмотрел gmp.
Сделал пару тестов и понял, что в общем эта библиотека делает все то же, но только в профиль.
Там есть функция mpz_probab_prime_p, которая находит все те же как бы простые числа, хотя и с какой угодно высокой долей вероятности.
Для проверки используется все тот же алгоритм: сначала число просеиваем с помощью начальной таблицы простых чисел, а потом делаем вероятностный тест Миллера.
Я попробовал с помощью gmp сгенерить простое число в 10000 знаков. после чего мой комп впал в ступор.
Вывод: современные персоналки непригодны для решения подобных задач.