Номер §30, страница 341 - гдз по алгебре 8 класс учебник Мерзляк, Поляков

Дружим с компьютером - номер §30, страница 341.

Условие.

K § 30 «Простые и составные числа»

Запишите алгоритм определения того, является ли данное натуральное число простым.

Запишите алгоритм для получения канонического разложения составного числа на простые множители.

* Напишите программу для выдачи первых $n$ простых чисел. Оцените временные характеристики её работы. Какое максимальное натуральное число может быть представлено в выбранном вами языке программирования и какие ограничения это накладывает на возможности вашей программы?

Найдите в сети Интернет информацию о простых числах, об истории составления таблиц простых чисел и о том, какие результаты достигнуты на текущий момент.

Решение.

Запишите алгоритм определения того, является ли данное натуральное число простым.

Простое число — это натуральное число больше 1, которое имеет ровно два различных натуральных делителя: 1 и самого себя. Алгоритм для проверки, является ли число $n$ простым, может быть следующим (метод перебора делителей):

1. Получить на вход натуральное число $n$.
2. Если $n \le 1$, то число не является простым (по определению). Завершить алгоритм.
3. Если $n = 2$, то число является простым. Завершить алгоритм.
4. Если $n$ делится на 2 без остатка (т.е. $n$ — чётное), то оно не является простым (т.к. уже имеет делитель 2). Завершить алгоритм.
5. Если $n$ — нечётное число больше 2, то нужно проверить наличие у него делителей. Поскольку все чётные делители уже исключены, можно проверять только нечётные числа. Делители достаточно искать в диапазоне от 3 до $\sqrt{n}$. Если у числа $n$ есть делитель $d > \sqrt{n}$, то обязательно должен быть и делитель $k = n/d < \sqrt{n}$, который был бы найден раньше.
6. Запустить цикл с переменной $i$, начинающейся с 3, с шагом 2 (т.е. перебирая $3, 5, 7, ...$) до тех пор, пока $i \le \sqrt{n}$.
7. Внутри цикла проверять, делится ли $n$ на $i$ без остатка. Если делится, то найден делитель, отличный от 1 и $n$. Значит, число $n$ является составным. Завершить алгоритм.
8. Если цикл завершился, и ни один делитель не был найден, то число $n$ является простым.

Ответ: Вышеописанный алгоритм пробного деления позволяет определить, является ли натуральное число простым, путем проверки делимости этого числа на все простые числа (или просто нечетные числа) до его квадратного корня.

Запишите алгоритм для получения канонического разложения составного числа на простые множители.

Каноническое разложение числа — это представление этого числа в виде произведения степеней простых чисел. Например, $360 = 2^3 \cdot 3^2 \cdot 5^1$.

Алгоритм для нахождения такого разложения для числа $n$:

1. Получить на вход составное число $n$. Инициализировать пустой список для хранения простых множителей.
2. Начать с наименьшего простого делителя $d = 2$.
3. Запустить цикл, который продолжается, пока $d \cdot d \le n$.
   • Внутри этого цикла запустить другой (вложенный) цикл: пока $n$ делится на $d$ без остатка, добавлять $d$ в список множителей и делить $n$ на $d$ (то есть $n = n / d$).
   • После того как $n$ перестало делиться на $d$, увеличить $d$. Можно просто увеличивать на 1 ($d=d+1$) или использовать более оптимальный шаг (сначала проверить 2, потом перебирать только нечётные числа $3, 5, 7, ...$).
4. После завершения основного цикла (когда $d \cdot d > n$), если оставшееся значение $n$ больше 1, то это $n$ также является простым множителем. Его нужно добавить в список.
5. Сгруппировать одинаковые множители из списка и записать их в виде степеней для получения канонической формы.

Пример для числа 360:

• $n = 360, d = 2$. $360 \% 2 == 0$. Множители: [2]. $n = 180$.
• $n = 180, d = 2$. $180 \% 2 == 0$. Множители: [2, 2]. $n = 90$.
• $n = 90, d = 2$. $90 \% 2 == 0$. Множители: [2, 2, 2]. $n = 45$.
• $n = 45, d = 2$. $45 \% 2 \ne 0$. Увеличиваем $d$ до 3.
• $n = 45, d = 3$. $45 \% 3 == 0$. Множители: [2, 2, 2, 3]. $n = 15$.
• $n = 15, d = 3$. $15 \% 3 == 0$. Множители: [2, 2, 2, 3, 3]. $n = 5$.
• $n = 5, d = 3$. $5 \% 3 \ne 0$. Увеличиваем $d$ до 4 (пропускаем), затем до 5.
• $d = 5$. Условие $d \cdot d \le n$ (т.е. $25 \le 5$) не выполняется. Цикл завершается.
• Оставшееся $n = 5$. Так как $5 > 1$, добавляем 5 в список. Множители: [2, 2, 2, 3, 3, 5].
• Группируем: три двойки ($2^3$), две тройки ($3^2$), одна пятёрка ($5^1$).

Ответ: Алгоритм последовательно делит исходное число $n$ на наименьшие возможные простые делители, начиная с 2, пока $n$ не станет равным 1. Найденные делители и составляют его каноническое разложение.

* Напишите программу для выдачи первых n простых чисел. Оцените временные характеристики её работы. Какое максимальное натуральное число может быть представлено в выбранном вами языке программирования и какие ограничения это накладывает на возможности вашей программы?

Для эффективной генерации последовательности простых чисел лучше всего подходит алгоритм "Решето Эратосфена". Однако, он генерирует простые числа до некоторого предела, а не заданное их количество. Чтобы найти первые $n$ простых чисел, нужно сначала оценить, где примерно находится $n$-ое простое число ($p_n$). Согласно теореме о распределении простых чисел, $p_n \approx n \ln n$. Для надежности можно взять верхнюю границу с запасом, например, $M = n (\ln n + \ln \ln n)$ для $n \ge 6$.

Программа на Python

Программа будет использовать Решето Эратосфена для нахождения всех простых чисел до вычисленной верхней границы $M$, а затем вернет первые $n$ из них.

import mathdef get_first_n_primes(n): "" Возвращает список первых n простых чисел. "" if n <= 0: return [] if n == 1: return [2] # Оценка верхнего предела для n-го простого числа if n < 6: limit = 15 # Для малых n берем предел с запасом else: # p_n < n(ln n + ln ln n) for n >= 6 limit = int(n * (math.log(n) + math.log(math.log(n)))) + 1 primes = [] is_prime = [True] * (limit + 1) is_prime[0] = is_prime[1] = False for p in range(2, int(math.sqrt(limit)) + 1): if is_prime[p]: for i in range(p * p, limit + 1, p): is_prime[i] = False count = 0 for num in range(2, limit + 1): if is_prime[num]: primes.append(num) count += 1 if count == n: break return primes# Пример использования:n = 10first_n_primes = get_first_n_primes(n)print(f"Первые {n} простых чисел: {first_n_primes}")# Вывод: Первые 10 простых чисел: [2, 3, 5, 7, 11, 13, 17, 19, 23, 29] 

Оценка временных характеристик её работы

Временная сложность алгоритма "Решето Эратосфена" для нахождения всех простых чисел до $M$ составляет $O(M \log \log M)$. В нашей задаче $M$ оценивается как $O(n \ln n)$. Таким образом, общая временная сложность программы составляет примерно $O(n \ln n \log \log (n \ln n))$. Это очень эффективный алгоритм для генерации большого количества простых чисел.

Максимальное натуральное число и ограничения

В языке программирования Python стандартные целые числа (тип `int`) имеют произвольную точность. Это означает, что максимальное значение целого числа ограничено только объемом доступной оперативной памяти (RAM) компьютера, а не фиксированным количеством байт (как, например, 64-битные целые в C++ или Java, которые ограничены числом $2^{63}-1$).

Это накладывает следующие ограничения на программу:

1. Ограничение по памяти: Основным ограничением для данной реализации является размер списка `is_prime` (булев массив для решета). Его размер равен `limit + 1`, где `limit` $\approx n \ln n$. Если мы захотим найти очень большое количество простых чисел (например, первый миллиард), то `limit` станет огромным, и для хранения списка `is_prime` может не хватить оперативной памяти. Например, для $n=10^9$ `limit` будет порядка $2 \cdot 10^{10}$, что потребует около 20 гигабайт памяти только для списка `is_prime`.
2. Ограничение по времени: Хотя сложность алгоритма хорошая, для очень больших $n$ время выполнения все равно будет значительным. Операции с очень большими числами (которые не помещаются в регистры процессора) выполняются медленнее, чем с числами машинного размера.

Ответ: Представлена программа на Python, использующая Решето Эратосфена, с временной сложностью $O(n \ln n \log \log (n \ln n))$. Максимальное натуральное число в Python ограничено только доступной памятью, что делает память основным ограничивающим фактором для работы программы при поиске большого количества простых чисел.

Найдите в сети Интернет информацию о простых числах, об истории составления таблиц простых чисел и о том, какие результаты достигнуты на текущий момент.

Простые числа — фундаментальный объект изучения в теории чисел. Их исследование имеет долгую и богатую историю.

История изучения и составления таблиц

• Древняя Греция: Евклид в своих "Началах" (около 300 г. до н.э.) доказал, что простых чисел бесконечно много. Эратосфен (III век до н.э.) придумал свой знаменитый алгоритм "решето" для нахождения простых чисел, который является первым систематическим методом их поиска.
• Средние века и Новое время: Математики продолжали составлять таблицы простых чисел вручную. В 1770-х годах Антуан Фелькель и другие математики расширили таблицы до нескольких миллионов. Эти таблицы были важны для проверки гипотез, таких как теорема о распределении простых чисел. Карл Фридрих Гаусс, изучая эти таблицы, предположил, что плотность простых чисел вблизи $x$ составляет примерно $1 / \ln(x)$.
• XX век и эра компьютеров: С появлением компьютеров составление таблиц и проверка чисел на простоту вышли на новый уровень. Стало возможным проверять огромные числа и находить простые числа, состоящие из миллионов цифр.

Современные результаты и достижения

• Самое большое известное простое число: На начало 2024 года, самым большим известным простым числом является $2^{82,589,933} - 1$. Это число Мерсенна, оно содержит 24,862,048 десятичных цифр. Оно было найдено в декабре 2018 года в рамках проекта распределенных вычислений GIMPS (Great Internet Mersenne Prime Search).
• Вычисление количества простых чисел: Математики научились вычислять точное количество простых чисел $\pi(x)$ до очень больших значений $x$. Например, известно точное значение $\pi(10^{28})$.
• Нерешённые проблемы: Несмотря на значительный прогресс, многие фундаментальные вопросы о простых числах остаются без ответа. К ним относятся:
  • Гипотеза Римана: связана с распределением нулей дзета-функции Римана и имеет глубокие следствия для распределения простых чисел.
  • Гипотеза Гольдбаха: утверждает, что любое чётное число, большее двух, можно представить в виде суммы двух простых чисел. Проверена для чисел до $4 \cdot 10^{18}$, но не доказана в общем виде.
  • Проблема простых чисел-близнецов: предполагает, что существует бесконечно много пар простых чисел, отличающихся на 2 (например, 11 и 13). В 2013 году Итан Чжан совершил прорыв, доказав, что существует бесконечно много пар простых чисел, расстояние между которыми не превышает 70 миллионов. Позже этот предел был снижен до 246.

Ответ: Изучение простых чисел началось в Древней Греции и продолжается по сей день с использованием мощных компьютеров. На данный момент найдено простое число, содержащее почти 25 миллионов цифр, но многие ключевые гипотезы, такие как гипотеза Римана и проблема чисел-близнецов, до сих пор не доказаны.