Тапсырмалар № 25, 26 · ЕГЭ

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

Определение и проверка простоты числа

2 мин чтенияҚиындық: Обновлено 29 қыркүйек 2026

Простое число — это натуральное число, которое имеет ровно два натуральных делителя: $1$ и само себя. Для проверки простоты достаточно искать делители не больше квадратного корня из числа.

Простое числоТермин связан с идеей неделимости числа на меньшие множители, кроме $1$ и самого числа.

Простое число — натуральное число, большее $1$, у которого ровно два различных натуральных делителя: $1$ и само число. Например, $2$, $3$, $5$, $7$ и $11$ — простые числа.

Понятие простого числа использует теория чисел и опирается на делимость чисел. Число, большее $1$, бывает либо простым, либо составным. Составное число имеет более двух натуральных делителей и представляется произведением меньших натуральных чисел.

Как проверить простоту

Прямой способ — перебрать возможные делители $d$ от $2$ до $n-1$. Если найдено число, на которое $n$ делится без остатка, то $n$ составное. Однако достаточно проверять делители только до $\sqrt{n}$: если $n=a\cdot b$, где оба множителя больше $\sqrt{n}$, их произведение было бы больше $n$.

\[n\text{ простое} \Longleftrightarrow n>1\text{ и для всех }d\in\{2,\ldots,\lfloor\sqrt{n}\rfloor\}:\ n\bmod d\ne 0\]

Алгоритм сначала отдельно обрабатывает числа $n\le 1$: они не являются простыми. Затем проверяет делители от $2$ до $\lfloor\sqrt{n}\rfloor$. Если ни один не подошёл, число простое. Такой алгоритм выполняется за $O(\sqrt{n})$ проверок.

№

Пример: число 29

$\sqrt{29}\approx5{,}38$, поэтому проверяем только $2$, $3$ и $5$. Число $29$ не делится ни на одно из них, значит, у него нет делителей, кроме $1$ и $29$. Следовательно, $29$ — простое.

Не путайте с единицей

Число $1$ не является простым: у него только один натуральный делитель — $1$. Число $2$ — простое и единственное чётное простое число.

Проверь себя

Какое из чисел является простым?

Главное за минуту

Главное

Простое число больше $1$ и имеет ровно два натуральных делителя: $1$ и само себя.
Для проверки простоты достаточно проверить делители до $\lfloor\sqrt{n}\rfloor$.
Число $1$ не является простым, а $2$ — единственное чётное простое число.