Проверка числа на простоту

Алгоритм проверки, является ли число простым, за O(√n)

🐍 Python

x = int(input())
i = 2
while i * i <= x:
    if x % i == 0:
        print("composite")
        exit()
    i += 1
print("prime")

⚙️ C++

#include <bits/stdc++.h>
using namespace std;

int main() {
    long long x;
    cin >> x;
    
    for (long long i = 2; i * i <= x; i++) {
        if (x % i == 0) {
            cout << "composite" << endl;
            return 0;
        }
    }
    
    cout << "prime" << endl;
    return 0;
}

Как проверить число на простоту?

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

Алгоритм проверки

Достаточно проверить делители до √n, потому что если число n имеет делитель d > √n, то соответствующий ему делитель n/d будет меньше √n.

Если n = a·b и a ≤ b, то a ≤ √n

Сложность: O(√n) — проверяем все числа от 2 до √n.

Особые случаи

Числа 0 и 1 не являются простыми
2 — единственное чётное простое число
Можно оптимизировать, проверяя сначала делимость на 2, а затем только нечётные числа

Формат ввода и вывода

Ввод: одно целое число x (x ≥ 2)

Вывод:

prime — если число простое
composite — если число составное

Пример 1:

Вывод: prime

Пример 2:

Вывод: composite (12 = 2 × 6)

Попробовать онлайн

Число x:

Результат появится здесь...