4.7. В результате описанной в условии задачи процедуры в ряду чисел от 1 до л не будет зачеркнуто ни одно простое число, так как на каждом шагу зачеркиваются только числа, кратные каким-то другим числам. Число k (большее 1) из этого ряда останется незачеркнутым только в том случае, если оно не делится ни на одно из незачеркнутых чисел, не превосходящих 
, среди которых содержатся все простые числа, не превосходящие 
Согласно задаче 4.5, таким числом к может быть только простое число. Таким образом, в ряду останутся незачеркнутыми все простые числа и только они.
4.8. Зачеркнув в ряду чисел от 1 до 100 сначала число 1, затем числа, кратные 2, кроме числа 2, затем числа, кратные 3, кроме числа 3, затем числа, кратные 5, кроме числа 5, и, наконец, числа, кратные 7, кроме числа 7, мы получим следующий набор незачеркнутых чисел:
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97. На этом следует остановиться, поскольку следующее за числом 7 незачеркнутое число 11 уже превосходит 
4.9. Так как 
то наименьший простой делитель любого из составных чисел, меньших 150, не превосходит 11 (см. задачу 4.5). Вычеркнем из ряда чисел от 120 до 150 все числа, делящиеся на 2, 3 или 5, тогда останутся числа
121, 127, 131, 133, 137, 139, 143, 149. Учитывая, что число 121 делится на 11, а число 140 - на 7, находим среди оставшихся чисел все числа, кратные 11 или 7. Вычеркнув их, мы получаем ответ:
127, 131, 137, 139, 149. 4.10. Число не делится ни на 2, ни на 3, ни на 5 в том и только в том случае, если его остаток от деления на 30=2x3x5 не делится ни на одно из этих чисел. Так как
то, вычеркнув из всех возможных значений остатков от деления на 30, т. е. из чисел от 0 до 29, числа, кратные 2, 3 или 5, мы получим число 1 и все простые числа (см. задачу 4.7). Следовательно, набор искомых остатков выглядит так:
1, 7, 11, 13, 17, 19, 23, 29. Благодаря этому наблюдению при отыскании простых чисел (больших 5) можно выписывать не все числа подряд, а только те, которые дают указанные здесь восемь остатков от деления на 30, что позволяет сэкономить работу по выписыванию в 30/8 = 3,75 раза. Именно так можно было поступить, например, при решении задачи 4.9.
4.11. Так как 
то наименьший простой делитель любого из составных чисел, меньших 520, не превосходит 19 (см. задачу 4.5). Согласно результату задачи 4.10, простые числа могут оказаться лишь среди 12 чисел
473, 479, 481, 487, 491, 493, 497, 499, 503, 509, 511, 517. Из этих чисел теперь остается только вычеркнуть числа, кратные 7 (497, 511), кратные 11 (473, 517), кратные 13(503), кратные 17 (493) и кратные 19 (таких нет), и получить окончательный набор
479, 481, 487, 491, 499, 509.
§ 5. Вокруг наибольшего общего делителя
Одна из простейших задач, для решения некоторой понадобится найти наибольший общий делитель пары натуральных чисел а и b,- это 1 задача сокращения дроби a/b. Напомним, что если числа а и b делятся на одно и то же натуральное число d, то число d называется общим делителем пары чисел а и b. Любая пара натуральных чисел имеет хотя бы один общий делитель (а именно, d = 1), причем любой общий делитель не превосходит каждого из этих чисел. Поэтому среди всех делителей чисел а и b можно выбрать наибольший общий делитель, который обозначается через (а, b), например (20, 100) = 20, (65, 39) = 13. Если (а, b) = 1, то числа а и b называются взаимно простыми. При этом взаимно простые числа а и b совсем не обязательно сами по себе должны быть простыми числами; так, (33, 35) = 1, но 33 = 3*11 и 35 = 5*7.
У читателя, возможно, сложилось впечатление, что нахождение наибольшего общего делителя пары чисел представляет собой очень простую задачу. Ведь если разложить на простые множители каждое из данных чисел, то сразу станет ясно, как составить из этих простых множителей наибольшее произведение, на которое делятся оба данных числа. Однако все дело в том, что разложить число на простые множители иногда бывает довольно трудно, тогда как нахождение наибольшего общего делителя можно осуществить намного проще - с помощью несложной процедуры. Эта процедура известна уже более 2 тысяч лет и носит название алгоритма Евклида.
Алгоритм Евклида применяется ко многим с виду разнородным объектам. Нахождение наибольшего общего делителя, разложение дроби в цепную дробь, приближение дроби более простыми, решение уравнений в целых числах - вот далеко не полный перечень приложений этого алгоритма, с которыми вы познакомитесь в настоящем и следующем параграфах.