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

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

35
2. Сделайте программу немного более эффективной для полного иг-
норирования чётных чисел, а использование массива key[1 . . 999] соответ-
ствовало бы только нечётным числам 3, 5, 7, . . . , 1999. Наконец, 2i + 1 бу-
дет простым числом только если a[i] = TRUE.
8.2*. Компьютерное упражнение. Используйте решето Лежандра
для нахождения
π
(x), где x = 10
5
, 2 · 10
5
, 3 · 10
5
, . . . , 10
6
. Для x = 6 · 10
5
S
i
будет равняться: 599 999, 1297 809, 1 263 496, 698 663, 207 842, 26 863,
961, 2; также
π
()
x = 137, давая для целого
π
(x) = 49 098.
8.3*. Проект: Li (x) и Ri(x) снова. Найдите функции Li (x) и Ri(x)
(см. выше) для значений х из п. 8.2. Найдите также x/ln x для тех же значе-
ний х и постройте графики зависимости х от этих трёх функций, а также
действительное значение функции
π
(х). Какая аппроксимация подходит
лучше?
8.4. Компьютерное упражнение. Используйте программу для нахо-
ждения
π
(1000),
π
(2000),
π
(3000) и
π
(4000). Вы можете заметить, что это
получение решения протекает крайне медленно во времени. Попробуйте
рассчитать значительно меньший пример вручную, чтобы выяснить, почему
это происходит. Сумеете ли Вы ускорить выполнение программы?
8.5. Проект: счастливые числа. Существует другое сито, во многом
похожее на решето Эратосфена, которое даёт другую последовательность чи-
сел с распределением почти как у простых чисел. Действительно, можно ска-
зать, что распределение простых чисел будет меньше их «простоты», чем на
самом деле они могут генерироваться решетом. Представим это решето. Нач-
нём, как и ранее,
с положительных целых чисел. Будем вычёркивать каждое
второе целое число в списке, начиная счёт с 1 (таким образом Вы вычеркните
2, 4, 6, . . .). Следующее малое число слева будет 3, и мы вычеркнем каждое
третье число, начиная счёт с 1 (вычеркнем 5, 11, 17, . . .). Теперь 7 – наимень-
шее целое число слева от 3, аналогичным образом вычеркнем все седьмые
числа слева, начиная с 1.
Это может продолжаться неопределённо долго. Чис-
ла, которые остаются после этой процедуры, будут счастливые числа. Напи-
шите программу для поиска всех счастливых чисел < 10 000. Проверьте, будут
ли следующие цифры L(x) счастливыми числами ≤ x:
x 10
3
2
× 10
3
3 × 10
3
4 × 10
3
5 ×
10
3
6 × 10
3
7 × 10
3
8 × 10
3
9 ×10
3
10
4
L(x) 153 276 390 503 610 716 816 920 819 918
Каким образом связать эти значения с «теоремой о счастливых чис-
лах» вида L(x) = x/ln x?
Сделаем некоторые подсказки перед написанием программы. Оши-
бочным было бы использовать единственный массив для хранения, скажем,

Страницы