4.4. Составные числа - соседи Найдите пять последовательных натуральных чисел, каждое из которых является составным. Для любого ли натурального значения n можно подобрать n таких чисел?
4.5. Простое или составное? Чтобы узнать, является ли данное натуральное число n составным, достаточно проверить, имеет ли оно хотя бы один делитель, больший 1 и меньший n. Докажите, что эту работу можно сократить, ограничившись проверкой делимости числа n только на простые числа и к тому же не превосходящие 
4.6. Простое или составное? Разложить на простые множители число: а) 315; б) 127; в) 1001; г) 899; д) 919.
4.7. Решето Эратосфена Выпишем подряд все натуральные числа от 1 до некоторого числа п и зачеркнем число 1. Возьмем первое незачеркнутое число, большее 1,- это будет число 2,- и зачеркнем каждое второе число, начиная отсчет от числа 2+1. Затем возьмем первое незачеркнутое число, большее 2,- это будет число 3,- и зачеркнем каждое третье число, начиная отсчет от числа 3 + 1 (ранее зачеркнутые числа также отсчитываются). Затем возьмем первое незачеркнутое число, большее 3,- это будет число 5,- и зачеркнем каждое пятое число, начиная отсчет от числа 5 + 1. Продолжая действовать так и далее, остановимся тогда, когда первое незачеркнутое число, большее предыдущего, окажется большим Докажите, что в итоге незачеркнутыми останутся все простые числа, не превосходящие n, и только они.
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. Предположим, что утверждение задачи не верно, т. е. простые числа образуют лишь конечное множество, состоящее из чисел p1, p2, ..., pn. Рассмотрим число
которое в силу основной теоремы арифметики делится хотя бы на одно из чисел p1, p2, ..., pn. Но тогда разность m - p1*p2*...*pn также делится на это число. С другой стороны, указанная разность равна 1 и не может делиться ни на одно из чисел p1, p2, ..., pn (больших 1). Полученное противоречие доказывает, что исходное предположение не верно, а утверждение задачи верно.
4.3. Если два простых числа идут подряд, то одно из них четно, а значит, равно 2 (см. решение задачи 4.1). Тогда второе число непременно равно 3, поскольку 1 не является простым числом. Итак, нами найдена единственная пара идущих подряд простых чисел. Отсюда следует, что тройки идущих подряд простых чисел не существует, так как из такой тройки можно было бы образовать две различные пары идущих подряд простых чисел, а именно первое число со вторым и второе с третьим.
4.4. Последовательные числа 24, 25, 26, 27, 28 образуют искомую пятерку. Докажем, что для любого натурального значения n найдутся n идущих подряд составных чисел. В самом деле, каждое из n чисел
является составным, поскольку число
делится на 2, 3, ..., n и n+1, откуда первое число (n+1)!+2 делится на 2, второе число (n+1)!+3 делится на 3,..., (n-1)-е число (n+1)!+n делится на n, а n-е число (n+1)!+(n+1) делится на n+1.
4.5. Докажем, что любое составное число n имеет простой делитель, не превосходящий 
Возьмем наименьшее простое число р, участвующее в разложении числа n на простые множители. Тогда число n представляется в виде произведения pq, причем p≤q, поэтому p2≤pq = n и 
Из доказанного утверждения следует, что если число n не делится ни на одно простое число, не превосходящее , то оно является простым.
4.6.
а) 315 = 32*5*7;
б) 127 - простое число, так как оно не делится ни на одно из простых чисел 2, 3, 5, 7, 11, не превосходящих 
в) 1001 = 7*11*13;
г) 899 = 302-12 = 29*31;
д) 919 - простое число, так как оно не делится ни на одно из простых чисел, не превосходящих