Страница 159 - гдз по математике 5 класс учебник Никольский, Потапов

714. a) Почему после «просеивания» чисел, кратных 2, 3, 5, 7, в таблице натуральных чисел от 1 до 100 остались только простые числа?

б) На каком числе следует остановить «просеивание», если в таблице будет 150; 10 000 первых натуральных чисел?

в) Используя «решето» Эратосфена, получите все простые числа в промежутке от 1 до 200.

а) Этот процесс, известный как «решето Эратосфена», основан на свойстве составных чисел. Любое составное число $N$ имеет хотя бы один простой делитель $p$, который не превышает квадратный корень из этого числа, то есть $p \le \sqrt{N}$.
Для таблицы чисел от 1 до 100 максимальное число $N = 100$. Квадратный корень из 100 равен 10, то есть $\sqrt{100} = 10$.
Следовательно, любое составное число от 1 до 100 обязательно имеет простой делитель, меньший или равный 10. Простыми числами в этом диапазоне являются 2, 3, 5 и 7.
Когда мы вычеркиваем («просеиваем») все числа, кратные 2, 3, 5 и 7, мы удаляем все составные числа в диапазоне до 100. Числа, которые не были вычеркнуты (кроме 1, которое по определению не является ни простым, ни составным), и являются простыми числами.
Ответ: Потому что любое составное число до 100 имеет простой делитель, не превосходящий 10, а простыми числами до 10 являются 2, 3, 5 и 7.

б) В общем случае, для нахождения всех простых чисел до $N$ с помощью «решета Эратосфена», процесс «просеивания» можно остановить после вычеркивания чисел, кратных всем простым числам $p$, удовлетворяющим условию $p \le \sqrt{N}$.

• Для таблицы из 150 натуральных чисел:
  Нужно найти простые числа, не превосходящие $\sqrt{150}$. Так как $12^2 = 144$ и $13^2 = 169$, то $\sqrt{150} \approx 12.25$.
  Простые числа, которые меньше или равны 12.25, это 2, 3, 5, 7, 11.
  Следовательно, «просеивание» следует остановить на простом числе 11.
• Для таблицы из 10 000 натуральных чисел:
  Нужно найти простые числа, не превосходящие $\sqrt{10000}$. $\sqrt{10000} = 100$.
  Самое большое простое число, не превосходящее 100, это 97.
  Следовательно, «просеивание» следует остановить на простом числе 97.

Ответ: Для 150 чисел — на числе 11; для 10 000 чисел — на числе 97.

в) Для нахождения всех простых чисел в промежутке от 1 до 200 с помощью «решета Эратосфена» необходимо выполнить следующие действия:
1. Выписать натуральные числа от 2 до 200.
2. Определить, до какого простого числа нужно производить «просеивание». Для этого находим $\sqrt{200} \approx 14.14$.
3. Простыми числами, не превосходящими 14.14, являются 2, 3, 5, 7, 11, 13.
4. Последовательно вычеркнуть из списка все числа, кратные 2, 3, 5, 7, 11 и 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.
Ответ: 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 = n^2 + n + 41$. Для любых ли натуральных $n$ число $P$ простое?

б) Сколько различных простых чисел можно получить по формуле $P = n^2 + n + 41$, если брать последовательные натуральные числа, начиная с $n = 1$?

а) Утверждение, что формула $P = n^2 + n + 41$ дает простое число для любого натурального $n$, является неверным. Чтобы это доказать, достаточно найти хотя бы один контрпример, то есть такое натуральное число $n$, при котором $P$ будет составным числом.

Рассмотрим выражение $P = n^2 + n + 41$. Его можно переписать в виде $P = n(n+1) + 41$.

Проверим значение $n=40$:
Подставим $n=40$ в формулу:
$P = 40^2 + 40 + 41 = 1600 + 40 + 41 = 1681$.
Число 1681 является составным, так как $1681 = 41^2 = 41 \times 41$.

Также можно проверить значение $n=41$:
$P = 41^2 + 41 + 41 = 41 \times (41 + 1 + 1) = 41 \times 43$.
Это число также является составным, так как оно делится на 41 и 43.

Поскольку мы нашли значение $n$, при котором число $P$ не является простым, утверждение неверно.
Ответ: нет, не для любых.

б) Нам нужно найти, сколько различных простых чисел можно получить, подставляя в формулу $P = n^2 + n + 41$ последовательные натуральные числа, начиная с $n=1$, до тех пор, пока результат не перестанет быть простым числом.

Будем вычислять значения $P$ для $n = 1, 2, 3, \ldots$ и проверять их на простоту:

• При $n=1$: $P = 1^2 + 1 + 41 = 43$ (простое)
• При $n=2$: $P = 2^2 + 2 + 41 = 47$ (простое)
• При $n=3$: $P = 3^2 + 3 + 41 = 53$ (простое)

...и так далее.

Известно, что данная формула (многочлен Эйлера) дает простые числа для всех целых $n$ от 0 до 39. Поскольку в задаче рассматриваются натуральные числа, начиная с $n=1$, формула будет давать простые числа для $n = 1, 2, \ldots, 39$. Всего получается 39 значений $n$.

Как мы выяснили в пункте а), при $n=40$ мы получаем составное число:
$P = 40^2 + 40 + 41 = 1681 = 41^2$.

Таким образом, последовательность простых чисел, генерируемых формулой, прерывается при $n=40$. Следовательно, мы получаем простые числа для 39 последовательных значений $n$: от 1 до 39.

Осталось убедиться, что все эти 39 простых чисел различны. Функция $P(n) = n^2+n+41$ является возрастающей для всех натуральных $n$. Это означает, что для разных значений $n$ мы будем получать разные значения $P$. Следовательно, все 39 полученных простых чисел будут различными.

Итак, по формуле можно получить 39 различных простых чисел, беря последовательные натуральные числа, начиная с $n=1$.
Ответ: 39.