zer0mail

Тысячи лет назад математики знали, что количество простых числ бесконечно и придумали простое доказателство "от противного":
Предположим, что простые числа образуют конечное множество: P1..PN (по возрастанию).
Перемномножим их все, прибавим 1 и получим число число P=P1*P2*..*PN . При делении на любое простое оно даест остаток 1, т .е. тоже простое и должно входить в P1..PN (там ведь все простые). А это невозможно, т.к. P больше всех Pn.
Перемножим подряд идущие простые (начиная с 2) и прибавим 1: P=2*3*..*Pk+1. Полученное число либо простое, либо делится на некоторое простое Px, большее Pk. Так и есть:
2+1=3
2*3+1=7
2*3*5+1=31

все полученные выше числа (для k=1,2,3) простые. Вопрос: для каких k число P не простое, чему оно равно и как раскладывается? Я написал программку для P<1млрд. Кто хочет, тоже может написать и узнать, сколько таких чисел (до выбранной им границы)

Интересно найти числа до триллиона (10^12), причем за разумное время и влезть в 4-8Гб памяти.

0

@likehood

Например число 2*3*5*7*11*13 + 1 = 30031 = 59*509 не является простым.

0

zer0mail

Можно искать такие k, для которых P=P1*..Pk+1 простое (они встречаются реже). Maple быстро просчитывает до P=1.5*10²⁰³⁷ при k=643 (Pk=4787). Даже не представляю, как она ухитряется это делать

Добавлено через 4 минуты
Верно. Дальше (умножение на 17,19,23) тоже дает непростые. И вообще - простые становятся редкими (31, 379, 1019,1021 (рядом), 2567,3229,4547,4787). А дальше - дыра...

0