ВУЗ:
Составители:
Рубрика:
31
Вы должны также сохранять информацию в программе о значениях p и oldp
(максимальном промежутке), и по окончании расчетов вывести на печать
результаты. Это должна быть наименьшая пара, дающая отмеченный мак-
симальный промежуток. Проверьте, что для max = 1500 максимальный
промежуток составляет 34, между 1327 и 1361. Определите максимальный
промежуток для max = 1000, max = 10 000. (Посмотрите снова абзац,
суще-
ствующий выше в п. 6.3).
6.8. Компьютерное упражнение. Для каких значений x функция про-
стого числа
π
(x) (= числу простых чисел ≤ x) равняется 500? Равна 5000?
6.9. Компьютерные упражнения
1. Проверьте, что каждое их чисел n = 29 341, 314 821, 172 081 и
564 651 обладает следующим свойством: n является произведением различ-
ных простых чисел p, а p – 1 является делителем числа n – 1 (такие числа
называются числами Кармайкла, и мы встретимся с ними ниже).
2. Разложите на множители десятичное число r
7
, чьё десятичное пред-
ставление имеет 7 единиц. В случае простых чисел, находящихся в файле,
содержащем до 100 000 простых чисел, программа уже не в состоянии фак-
торизовать число r
11
(имеющем 11 разрядов), так как один из сомножителей
оказывается >10
5
.
3. Разложите на множители числа 10
n
+ 1 для n = 9, 11, 15. (Для n = 11
Вы получите 11
2
· 23 · 4093 · 8779). Программа, однако, не в состоянии
справиться с n = 7, так как простой сомножитель оказывается >10
5
.
4. Разложите на простые сомножители 10
10
+ 18 и обратите внимание,
насколько медленно выполняется программа.
5. Попытайтесь проделать аналогичные действия с числом n = 500 000 002:
это число содержит простой делитель > 10
5
, так что не гарантируется достижение
полного разложения на множители.
6.10. Компьютерные упражнения
1. Напишите r
n
для десятичного числа, десятичное разложение кото-
рого состоит из n единиц. Используя r
n
с точностью extended, все числа
n = 7, 9, 11, 13, 15 могут быть представлены в виде произведения полно-
стью, используя п. 1.15. Проверьте это: например, r
15
= 3 × 31 × 37 × × 41 ×
× 271 × 2 906 161 содержит только один сомножитель больший 10
5
и то, что
он простой доказывается программой, так как для пробного деления ис-
пользовались все простые числа, вплоть до корня квадратного из числа.
С другой стороны, r
17
имеет два больших сомножителя, так что программа
не в состоянии представить это число в виде произведения простых чисел
(даже используя extended точность для описания чисел).
2. Представьте в виде произведения 10
n
+ 1 полностью для n = 12 и
n = 13. (Для n = 12 Вы получите 73 × 137 × 99 990 001).
Страницы
- « первая
- ‹ предыдущая
- …
- 29
- 30
- 31
- 32
- 33
- …
- следующая ›
- последняя »
