Простые числа, которые делятся только на 1 и на самих себя, на протяжении веков интриговали математиков и программистов. Проверка того, является ли число простым или нет, является фундаментальной проблемой теории чисел и часто встречается в задачах программирования. В этой статье мы рассмотрим несколько методов определения того, является ли число простым или нет, с использованием языка программирования C++. Мы предоставим примеры кода для каждого метода, что позволит вам понять детали реализации и выбрать наиболее подходящий подход для ваших конкретных требований.

Метод 1: Пробное деление
Метод пробного деления — один из самых простых и понятных способов проверки простых чисел. Он предполагает деление числа на все возможные делители до квадратного корня из числа и проверку остатков.

bool isPrime(int n) {
    if (n <= 1)
        return false;
    for (int i = 2; i * i <= n; i++) {
        if (n % i == 0)
            return false;
    }
    return true;
}

Метод 2: Решето Эратосфена
Решето Эратосфена — это эффективный алгоритм для поиска всех простых чисел до заданного предела. Однако его также можно адаптировать для проверки того, является ли конкретное число простым или нет.

bool isPrime(int n) {
    if (n <= 1)
        return false;
    vector<bool> sieve(n + 1, true);
    sieve[0] = sieve[1] = false;
    for (int i = 2; i * i <= n; i++) {
        if (sieve[i]) {
            for (int j = i * i; j <= n; j += i)
                sieve[j] = false;
        }
    }
    return sieve[n];
}

Метод 3: тест на простоту Миллера-Рабина
Тест на простоту Миллера-Рабина — это вероятностный алгоритм, который может с высокой степенью уверенности определить, является ли данное число простым. Он многократно применяет тест для определенного количества итераций, увеличивая вероятность правильности.

bool isPrime(int n) {
    if (n <= 1)
        return false;
    if (n <= 3)
        return true;
    if (n % 2 == 0 || n % 3 == 0)
        return false;
    int k = 5;
    while (k * k <= n) {
        if (n % k == 0 || n % (k + 2) == 0)
            return false;
        k += 6;
    }
    return true;
}

Метод 4: тест на простоту Ферма
Тест на простоту Ферма — это еще один вероятностный алгоритм, который может определить, является ли данное число простым. Он основан на Малой теореме Ферма и работает путем случайного выбора чисел и проверки, удовлетворяют ли они теореме.

bool isPrime(int n, int iterations) {
    if (n <= 1)
        return false;
    if (n <= 3)
        return true;
    while (iterations > 0) {
        int a = 2 + rand() % (n - 3);
        if (power(a, n - 1, n) != 1)
            return false;
        iterations--;
    }
    return true;
}
int power(int a, int b, int m) {
    if (b == 0)
        return 1;
    int result = power(a, b / 2, m);
    result = (result * result) % m;
    if (b % 2 == 1)
        result = (result * a) % m;
    return result;
}

В этой статье мы рассмотрели несколько методов проверки того, является ли число простым или нет, с использованием C++. Мы обсудили метод пробного деления, «Решето Эратосфена», а также два вероятностных теста, а именно тест на простоту Миллера-Рабина и тест на простоту Ферма. Каждый метод предлагает различные компромиссы с точки зрения простоты, эффективности и точности. Понимая эти методы, вы сможете принимать обоснованные решения при реализации алгоритмов проверки простых чисел в своих программах на C++.

Применяя эти методы проверки простых чисел в своих программах на C++, вы можете эффективно определить, является ли число простым или нет, открывая возможности для решения различных математических и программных задач.