Простое число
Материал из Algocode wiki
Версия от 10:53, 26 августа 2019; Romanchenko (обсуждение | вклад) (Определение и свойства простых чисел вынесены в отдельную статью)
Простые числа
Определение:
Простое число —это натуральное число, которое делится только на единицу и на себя. Единица при этом простым числом не считается.
Определение:
Составное число —это непростое число, отличное от единицы.
Примеры простых чисел: $2$, $3$, $5$, $179$, $10^9+7$, $10^9+9$.
Примеры составных чисел: $4$, $15$, $2^{30}$.
Еще одно определение простого числа: $N$ — простое, если у $N$ ровно два делителя. Эти делители при этом равны $1$ и $N$.
Некоторые свойства простых чисел
Вообще, про простые числа известно много свойств, но почти все из них очень трудно доказать. Вот некоторые из них:
- Простых чисел, меньших $N$, примерно $\frac{N}{\ln N}$.
- N-ое простое число равно примерно $N\ln N$.
- Простые числа распределены более-менее равномерно. Например, если вам нужно найти какое-то простое число в промежутке, то можно их просто перебрать и проверить — через несколько сотен какое-нибудь найдется.
- Для любого $N \ge 2$ на интервале $(N, 2N)$ всегда найдется простое число (Постулат Бертрана)
- Впрочем, существуют сколь угодно длинные отрезки, на которых простых чисел нет. Самый простой способ такой построить - это начать с $N! + 2$.
- Есть алгоритмы, проверяющие число на простоту намного быстрее, чем за корень.
- Максимальное число делителей равно примерно $O(\sqrt[3]{n})$. Это не математический результат, а чисто эмпирический — не пишите его в асимптотиках.
- Максимальное число делителей у числа на отрезке $[1, 10^5]$ — 128
- Максимальное число делителей у числа на отрекзке $[1, 10^9]$ — 1344
- Максимальное число делителей у числа на отрезке $[1, 10^{18}]$ — 103680
- Наука умеет факторизовать числа за $O(\sqrt[4]{n})$, но об этом как-нибудь в другой раз.
- Любое число больше трёх можно представить в виде суммы двух простых (гипотеза Гольдбаха), но это не доказано.
Автор конспекта: Полина Романченко
По всем вопросам пишите в telegram @Romanchenko