Навеяно вот этим:
http://algolist.manual.ru/maths/teornum/gene_prime.php
Товарищ Нестеренко описал алгоритм вычисления простых чисел. Вкратце суть такова:
1 Сначала вычисляем список начальных простых чисел - скажем, до миллиона или миллиарда
2 Берем последнее простое число в найденом списке и умножаем его на 4 плюс 2 - это будет R,
результат умножаем на последнее число в начальном списке и прибавляем единицу - получаем искомое число N
3 Первая проверка - N проверяем на простые делители из все того же начального списка
4 Вторая проверка - N проверяем с помощью алгоритма Рабина
5 Третья проверка - возводим двойку в степень N-1, результат делим на N
6 Четвертая проверка - возводим двойку в степень R , отнимаем единицу и проверяем на взаимную простоту с искомым числом N
Если все четыре проверки проходят, то N однозначно является простым числом.
На каждой итерации получается число с удвоенным количеством разрядов, если начинаем с 9999991, то уже на 7-й итерации
получаем простое число в тысячу знаков.
Все бы хорошо, но персоналный компьютер начинает вешаться уже после 5-й итерации.
Собственно, вопросы:
1. Существуют ли языки, кроме питона, позволяющие вычислять простые числа в 1000 и более знаков на основе встроенных
стандартных библиотек
2 Существуют ли специальные библиотеки, решающие эту задачу
Надеюсь, выбрал правильный раздел