Задание № 714
а) Почему после "просеивания" чисел, кратных 2, 3, 5, 7, в таблице натуральных чисел от 1 до 100 остались только простые числа?
б) На каком числе следует остановить "просеивание", если в таблице будет 150; 10000 первых натуральных чисел?
в) Используя "решето" Эратосфена, получите все простые числа в промежутке от 1 до 200.
Решение
а) Когда среди первых 100 натуральных чисел вычеркнули те, которые кратны простым числам 2, 3, 5, 7, вычеркнутыми оказались числа, кратные натуральным числам от 2 до 10. При этом в таблице будут вычеркнуты все остальные числа, так как наименьшее составное число, не делящееся ни на одно из натуральных чисел от 2 до 10, есть 11 * 11 = 121, но оно больше 100 и в таблице его нет.
б) Если чисел будет 150, то "просеивание" надо остановить на простом числе 11, так как при этом все числа, кратные натуральным числам от 2 до 12, окажутся вычеркнутыми. В этом случае в таблице будут вычеркнуты все составные числа, так как наименьшее составное число, не делящееся ни на одно из натуральных чисел от 2 до 12, есть 13 * 13 = 169, но оно больше 150 и в таблице его нет.
Если же чисел будет 10000, то "просеивание" надо остановить на простом числе 97, так как при это все числа, кратные натуральным числам от 2 до 100, окажутся вычеркнутыми. В этом случае в таблице будут вычеркнуты все составные числа, так как наименьшее составное число, не делящееся ни на одно из натуральных чисел от 2 до 100, есть 101 * 101 = 10201, но оно больше 10000 и в таблице его нет.
в) Чисел будет 200, "просеивание" надо остановить на простом числе 13, так как при этом все числа, кратные натуральным числам от 2 до 18, окажутся вычеркнутыми. В этом случае в таблице будут вычеркнуты все составные числа, так как наименьшее составное число, не делящееся ни на одно из натуральных чисел от 2 до 18, есть 17 * 17 = 289, но оно больше 200 и в таблице его нет.
Запишем числа от 1 до 200 в таблицу по 6 чисел в строке.
1 − не простое число и не составное − вычеркнем его.
Число 2 простое − обведем его кружком, а все числа, кратные ему (они стоят во втором, четвертом и шестом столбцах), вычеркнем.
Первое из незачеркнутых чисел 3. Оно простое − обведем его кружком, а все незачеркнутые числа, кратные ему (они стоят в третьем столбце), вычеркнем.
Теперь первое из незачеркнутых чисел 5. Оно простое − обведем его кружком, а все незачеркнутые числа, кратные ему (они расположены на параллельных прямых), вычеркнем.
Теперь первое из незачеркнутых чисел 7. Оно простое − обведем его кружком, а все незачеркнутые числа, кратные ему (они тоже расположены на параллельных прямых), вычеркнем.
Теперь первое из незачеркнутых чисел 11. Оно простое − обведем его кружком, а все незачеркнутые числа, кратные ему (их можно найти, выполняя шахматный ход конем), вычеркнем.
Теперь первое из незачеркнутых чисел 13. Оно простое − обведем его кружком, а все незачеркнутые числа, кратные ему (их также можно найти, выполняя шахматный ход конем), вычеркнем.
После вычеркивания из таблицы чисел, кратных 13, в ней останутся только простые числа − их тоже обведем кружком.
Простые числа в промежутке от 1 до 200: 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, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199.
Задание № 715
а) Петя придумал новую формулу для нахождения простых чисел:
P=n2+n+41.
Для любых ли натуральных n число P простое?
б) Сколько различных простых чисел можно получить по формуле:
P=n2+n+41,
если брать последовательные натуральные числа, начиная с n = 1?
Решение
а) Нет, так как для простого числа 41 число
P=412+41+41 делится на 1, на 41 и на P, то есть число P составное.
б) По формуле:
P=n2+n+41 можно получить множество простых чисел, если брать последовательные натуральные числа, начиная с n = 1, однако, если n кратно 41, то и результат
n2+n+41 будет кратным 41, то есть результат будет составным числом. Поэтому, при n = 1, 2, 3, 4, ..., 40 получается простое число, а при n = 41 получается составное число, кратное 41.
При n = 42, 43, 44, ..., 81 получается простое число, а при n = 82 получается составное число, кратное 41. И так далее.
