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

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

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

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

а)

Этот процесс называется «решето Эратосфена». Его суть в последовательном исключении составных чисел. Любое составное число $N$ можно представить в виде произведения $N = p \cdot k$, где $p$ — его наименьший простой делитель. При этом всегда выполняется условие $p \le \sqrt{N}$.

В нашей задаче мы ищем простые числа в диапазоне до 100. Найдём корень из 100: $\sqrt{100} = 10$. Это значит, что любое составное число до 100 обязательно будет иметь простой делитель, не превышающий 10.

Простыми числами, которые меньше или равны 10, являются 2, 3, 5 и 7.

Когда мы «просеиваем» (вычёркиваем) все числа, кратные 2, 3, 5 и 7, мы гарантированно вычёркиваем все составные числа в диапазоне до 100. Следующее простое число — 11. Наименьшее составное число, у которого наименьший простой делитель равен 11, это $11^2 = 121$. Это число уже больше 100 и выходит за пределы нашей таблицы.

Таким образом, после вычеркивания всех чисел, кратных 2, 3, 5 и 7, в таблице от 1 до 100 остаются только простые числа (и число 1, которое не является ни простым, ни составным).

Ответ: Потому что любое составное число до 100 имеет хотя бы один простой делитель из набора {2, 3, 5, 7}, так как квадрат следующего простого числа ($11^2=121$) больше 100.

б)

«Просеивание» следует останавливать на последнем простом числе $p$, которое удовлетворяет условию $p \le \sqrt{N}$, где $N$ — верхняя граница диапазона.

1. Если в таблице 150 чисел ($N=150$):
Найдём $\sqrt{150}$. Мы знаем, что $12^2 = 144$ и $13^2 = 169$. Значит, $\sqrt{150} \approx 12.25$.
Нам нужно найти наибольшее простое число, которое меньше или равно 12.25. Это число 11.
Следовательно, «просеивание» следует остановить на числе 11.

2. Если в таблице 10 000 чисел ($N=10000$):
Найдём $\sqrt{10000}$. $\sqrt{10000} = 100$.
Нам нужно найти наибольшее простое число, которое меньше или равно 100. Это число 97.
Следовательно, «просеивание» следует остановить на числе 97.

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

в)

Чтобы найти все простые числа в промежутке от 1 до 200, используем решето Эратосфена.

1. Определим предел «просеивания». Верхняя граница $N = 200$. Найдём $\sqrt{200}$. Так как $14^2 = 196$ и $15^2 = 225$, то $\sqrt{200} \approx 14.14$.
Простые числа, не превосходящие 14.14, это 2, 3, 5, 7, 11, 13. Будем последовательно вычеркивать числа, кратные им.

2. Выпишем числа от 2 до 200 (1 не является простым).

3. Вычеркнем все числа, кратные 2 (кроме самого 2): 4, 6, 8, ...

4. Вычеркнем все числа, кратные 3 (кроме самого 3): 6, 9, 12, ...

5. Вычеркнем все числа, кратные 5 (кроме самого 5): 10, 15, 20, ...

6. Вычеркнем все числа, кратные 7 (кроме самого 7): 14, 21, 28, ...

7. Вычеркнем все числа, кратные 11 (кроме самого 11): 22, 33, 44, ...

8. Вычеркнем все числа, кратные 13 (кроме самого 13): 26, 39, 52, ...

После выполнения всех этих действий останутся следующие числа:

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.

3.122. a) Петя придумал новую формулу для нахождения простых чисел: $P = n^2 + n + 41$. Для любых ли натуральных $n$ число $P$ простое?

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

а)

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

Проверим формулу для нескольких первых значений $n$:

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

Для малых $n$ формула действительно дает простые числа. Теперь попробуем найти контрпример. Заметим, что формулу можно представить в виде $P = n(n+1) + 41$. Если одно из слагаемых будет кратно 41, то и вся сумма может быть кратна 41.

Рассмотрим $n=40$. Подставим это значение в формулу:

$P = 40^2 + 40 + 41 = 1600 + 40 + 41 = 1681$.

Число 1681 является составным, так как оно равно $41^2$. Действительно, $1681 : 41 = 41$.

Используя преобразованную формулу:

$P(40) = 40(40+1) + 41 = 40 \times 41 + 1 \times 41 = (40+1) \times 41 = 41 \times 41 = 41^2$.

Так как мы нашли натуральное число $n=40$, при котором число $P$ является составным, то формула неверна для любых натуральных $n$.

Ответ: Нет, не для любых. Например, при $n=40$ число $P$ является составным.

б)

В этом пункте требуется найти, сколько различных простых чисел можно получить, подставляя в формулу $P = n^2 + n + 41$ последовательные натуральные числа, начиная с $n=1$. Это означает, что мы должны вычислять значения $P(n)$ для $n=1, 2, 3, \dots$ и остановиться, когда впервые получим составное число. Затем нужно посчитать количество простых чисел, которые мы получили до этого момента.

Из пункта а) мы знаем, что при $n=40$ формула дает составное число $P(40)=1681$.

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

Таким образом, мы получаем последовательность простых чисел при $n = 1, 2, 3, \dots, 39$. Количество таких значений $n$ равно 39.

Далее необходимо убедиться, что все эти 39 простых чисел являются различными. Рассмотрим функцию $P(n) = n^2 + n + 41$. При $n \ge 1$ эта функция является строго возрастающей, так как с увеличением $n$ оба слагаемых $n^2$ и $n$ увеличиваются, а значит, и их сумма $P(n)$ тоже увеличивается. Следовательно, для разных значений $n$ мы будем получать разные значения $P$.

Таким образом, для $n$ от 1 до 39 мы получим 39 различных простых чисел.

Ответ: 39.