Навеяно вот этим:
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 Существуют ли специальные библиотеки, решающие эту задачу
Надеюсь, выбрал правильный раздел
Похожие темы
- Форум Простые числа... (2013)
- Форум Простые числа. (2012)
- Форум [математикам] Простые числа (2011)
- Форум Незаконные простые числа (2014)
- Форум Простые числа C++ (2014)
- Форум [Большие простые числа] генерация... (2008)
- Форум Простые числа - не понимаю (2008)
- Форум Генерировать простые числа на haskell (2016)
- Форум Простые числа, факториалы и т.д. (2008)
- Форум [алгебра] простые числа и первое апреля (2011)