Элементы теории чисел и криптозащита. Воронков Б.Н - 30 стр.

UptoLike

ВУЗ: 

ВГУ | Воронеж

Составители: 

Рубрика: 

30
числа не запоминаются после того, как их найдут. Можно предложить вре-
менное хранение значения каждого найденного простого числа под именем,
подобным oldn, задав ему первоначальное значение 3 в начале программы
(объявив oldn и k даже ранее!) и проверяя каждое новое простое число на
соответствие n – oldn = k.
6.4. Компьютерное упражнение: промежутки между простыми
числами.
Используем вышеупомянутую идею приспособления программы
к выводу на печать простых чисел, отличающихся от предыдущего на вели-
чину k, которую вводит пользователь в программу. Найдите первые два по-
следовательных простых числа, которые отстоят друг от друга на
а) 10 единиц, б) 20 единиц. Что произойдёт, когда k = 25?
6.5. Компьютерное упражнение: двойные простые числа. Изменим
п. 6.3 так, чтобы использовать только случай k = 2, и вычислим количество
двойных простых чисел (начиная с 3, 5), меньших заданного максимального
числа. Проверьте, что таких пар 35 для чисел, меньших 1000, и 205 для чи-
сел, меньших 10 000. (Нетрудно догадаться, что двойных простых чисел ≤N,
а для больших N их количество можно найти по формуле
α
(ln )x
N
2
∫
–2
dx, где
α
≈ 1,3203236. Если Вы знакомы с квадратурной формулой Симпсона [3], то
сможете проверить это предположение).
6.6. Компьютерное упражнение: тройные простые числа.
Мы не
знаем, можно ли найти три простых числа вида p, p + 2, p + 4, кроме 3, 5, 7
(Почему бы нет?), зато существует множество примеров троек простых чи-
сел вида 6k – 1, 6k + 1, 6k + 5. Приспособим результаты расчетов по п. 6.3
выводить на печать все такие тройки простых чисел, которые меньше за-
данного максимума. Предполагаем, что существует
бесконечное множество
таких троек. Другой возможностью является рассмотрение квадруполей
простых чисел p, p + 2, p + 6, p + 8. Первыми двумя будут 5, 7, 11, 13 и 11,
13, 17, 19.
6.7. Компьютерное упражнение: наибольшие промежутки между
простыми числами
. Выбирая максимальное значение max, приспособим
программу находить наибольший промежуток между простыми числами,
возникающий у последовательных простых чисел, оба из которых ≤max.
Теперь нам необходимо сохранить запись максимального промежутка, ска-
жем, maxgap, и возобновлять его каждый раз, когда появляется простое
число p, отстоящее от предшествующего простого числа на больший про-
межуток oldp
:
IF p – oldp > maxgap THEN maxgap := p – oldp;

Страницы