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

Материал из Algocode wiki
Версия от 13: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