Что требуется?

Часть 1.

Лекция №4

Простые числа, генерация больших простых чисел, проверка на простоту.

!!! Предлагается ознакомиться с материалом на стр 1-14 самостоятельно для общей эрудиции, весьма любопытные и интересные сведения. Автор Ю.Матиясевич !!!

Простые числа разбросаны в натуральном ряду очень прихотливым образом, и не удивительно, что издревле математики стремились найти «формулу для простых чисел». Такими формулами можно называть формулы, обладающие разными свойствами, и здесь очень важно понять, что нам требуется на самом деле.

Самая простая формула для простых чисел выглядит, по-видимому, так:

где p_n обозначает n-е простое число. Чем же эта формула не устраивает нас? Дело в том, что правая часть этого равенства вычисляется слишком сложным образом — попробуйте, например, самостоятельно найти p₁₉₇₅! Мы же хотим получить аналогичную формулу с возможно более простым способом вычисления правой части (однако, как мы увидим, простота вычислений — понятие совсем не очевидное). Это, так сказать, программа-максимум.

Ради простоты формулы можно отказаться от требования явной зависимости от номера n и искать формулы, дающие простые числа, быть может, не по порядку. Далее, можно отказаться от желания задать одной формулой сразу все простые числа и требовать только того, чтобы формула давала бесконечно много простых чисел. Можно, наконец, допустить, чтобы эта формула давала наряду с бесконечно многими простыми числами и некоторые составные числа. Это — программа-минимум.

Формулы, кажущиеся очень простыми, на деле могут оказаться не лучше формулы (1). Именно к таким примерам мы сейчас и переходим.