Простое число

Простые числа

Определение:
Простое число —это натуральное число, которое делится только на единицу и на себя. Единица при этом простым числом не считается.

Определение:
Составное число —это непростое число, отличное от единицы.

Примеры простых чисел: $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