ВУЗ:
Составители:
Рубрика:
32
3. Представьте в виде произведения 2
32
+ 1 (пятое число Ферма).
4. Измените программу факторизации целых чисел так, чтобы она ни-
чего не распечатывала бы, если n – составное число, и печатала бы, если n –
простое число. (Вам потребуется сохранять первоначальное число n, как,
скажем, n
0
, исключая печать (prime: 0: 0). Найдите первые 100 простых чи-
сел, которые имеют вид k
2
+ 1 для целого k (наименьшим будет 2 (k = 1), а
наибольшим будет 739 601 (k = 860)).
5. Испытайте n = 10
10
+ 18 и заметьте, насколько быстрее выполняется
текущая программа по сравнению с первым вариантом программы факто-
ризации. Испытайте также 500 000 002 снова и заметьте, что полное разло-
жение на простые сомножители достигается, так как последнее содержит
простой сомножитель < 10
10
.
6. Испытайте n = 10 113 949 037. Какое число будет наибольшим, ко-
торое можно получить на выходе программы?
6.11. Проект: число простых сомножителей числа n
Для некоторого n ≥ 1, функция
Ω
(n) определяется как общее число
простых делителей n (
Ω
(1) принимается равной нулю). Таким образом,
200 = 2
3
× 5
2
, отсюда
Ω
(200) = 3 + 2 = 5. (Существует также функция
ω
, ко-
торая сосчитывает различные простые сомножители n :
ω
(200) = 2). При-
способим программу для нахождения
Ω
(n). Пусть f(n) = ()−
=
∑
1
1k
n
Ω
(k)
k
–2
Оцените величину f(n) при n → ∞ .
6.12. Проект: 4n + 1 против 4n – 1.
Все простые числа, кроме 2,
имеют одну из этих двух форм, а вот распределение этих двух типов дает
интересные результаты. Проверьте, что 11 593 является первым в последо-
вательности простых чисел вида 4n + 1. Проверьте, что наименьшим N, для
которого (число простых чисел ≤ N вида 4n + 1) больше (числа простых чи-
сел ≤ N
вида 4n – 1) будет N = 26 861. (Таким образом, простые числа вида
4n – 1 доминируют в списке «малых» простых чисел). Заметим, что сущест-
вует бесконечное множество чисел как первого, так и второго вида.
6.13. Проект. Можно показать, что существует целое число N ≤ 100
такое, что для всех n ≥ N, по крайней мере, одно из чисел n, n + 1, n + 2, . . . ,
n + 9 имеет три или более различных простых сомножителей. Напишите
программу, воплощающую эту прекрасную догадку для числа n.
6.14. Компьютерное упражнение. Проверьте, что существуют 11
простых чисел между 10
4
и 10
4
+ 100. Найдите простые числа между 10
n
и
10
n
+ 100 для n = 5, 6, 7, 8. Проделайте то же самое для простых чисел меж-
ду 10
n
и 10
n
+ 1000 (для n = 8 существуют 54 таких простых числа).
Страницы
- « первая
- ‹ предыдущая
- …
- 30
- 31
- 32
- 33
- 34
- …
- следующая ›
- последняя »
