Примени математику (Гашков, Сергеев) - страница 27
4.6. Простое или составное? Разложить на простые множители число: а) 315; б) 127; в) 1001; г) 899; д) 919.
4.7. Решето Эратосфена Выпишем подряд все натуральные числа от 1 до некоторого числа п и зачеркнем число 1. Возьмем первое незачеркнутое число, большее 1,- это будет число 2,- и зачеркнем каждое второе число, начиная отсчет от числа 2+1. Затем возьмем первое незачеркнутое число, большее 2,- это будет число 3,- и зачеркнем каждое третье число, начиная отсчет от числа 3 + 1 (ранее зачеркнутые числа также отсчитываются). Затем возьмем первое незачеркнутое число, большее 3,- это будет число 5,- и зачеркнем каждое пятое число, начиная отсчет от числа 5 + 1. Продолжая действовать так и далее, остановимся тогда, когда первое незачеркнутое число, большее предыдущего, окажется большим
4.8. Первые 25 простых чисел Используя решето Эратосфена, выпишите все простые числа, не превосходящие 100.
4.9. Еще несколько простых чисел Выпишите все простые числа, находящиеся между числами 120 и 150.
4.10. Эйлерова модификация решета Описанную в задаче 4.7 процедуру отыскания простых чисел можно упростить, если с самого начала не выписывать чисел, кратных 2, 3 или 5: Найдите все остатки от деления на 30, которые могут давать числа, не делящиеся ни на 2, ни на 3, ни на 5.
4.11. Попробуйте сами Выпишите все простые числа, находящиеся между числами 470 и 520.
Решения
4.1. Все четные числа, большие 2 (а их бесконечно много), являются составными, так как каждое из них делится на 1, на себя и на 2.
4.2. Предположим, что утверждение задачи не верно, т. е. простые числа образуют лишь конечное множество, состоящее из чисел p>1, p>2, ..., p>n. Рассмотрим число
которое в силу основной теоремы арифметики делится хотя бы на одно из чисел p>1, p>2, ..., p>n. Но тогда разность m - p>1*p>2*...*p>n также делится на это число. С другой стороны, указанная разность равна 1 и не может делиться ни на одно из чисел p>1, p>2, ..., p>n (больших 1). Полученное противоречие доказывает, что исходное предположение не верно, а утверждение задачи верно.
4.3. Если два простых числа идут подряд, то одно из них четно, а значит, равно 2 (см. решение задачи 4.1). Тогда второе число непременно равно 3, поскольку 1 не является простым числом. Итак, нами найдена единственная пара идущих подряд простых чисел. Отсюда следует, что тройки идущих подряд простых чисел не существует, так как из такой тройки можно было бы образовать две различные пары идущих подряд простых чисел, а именно первое число со вторым и второе с третьим.