Чтобы проверить, является ли число простым в C++, можно использовать несколько методов. Вот несколько часто используемых подходов:

Метод 1: базовое деление
В этом методе вы можете проверить, является ли число n простым, разделив его на все числа от 2 до sqrt(n). Если в результате любого из делений остаток равен 0, то число не является простым.

#include <iostream>
#include <cmath>
bool isPrime(int n) {
    if (n <= 1)
        return false;
    for (int i = 2; i <= sqrt(n); i++) {
        if (n % i == 0)
            return false;
    }

    return true;
}
int main() {
    int number;
    std::cout << "Enter a number: ";
    std::cin >> number;
    if (isPrime(number))
        std::cout << number << " is a prime number.";
    else
        std::cout << number << " is not a prime number.";

    return 0;
}

Метод 2: оптимизированное деление
Этот метод аналогичен базовому методу деления, но включает в себя несколько оптимизаций. Он проверяет делимость только нечетных чисел и пропускает четные числа больше 2.

#include <iostream>
#include <cmath>
bool isPrime(int n) {
    if (n <= 1)
        return false;
    if (n == 2)
        return true;
    if (n % 2 == 0)
        return false;
    for (int i = 3; i <= sqrt(n); i += 2) {
        if (n % i == 0)
            return false;
    }
    return true;
}
int main() {
    int number;
    std::cout << "Enter a number: ";
    std::cin >> number;
    if (isPrime(number))
        std::cout << number << " is a prime number.";
    else
        std::cout << number << " is not a prime number.";

    return 0;
}

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

#include <iostream>
#include <vector>
void sieveOfEratosthenes(int n) {
    std::vector<bool> primes(n + 1, true);
    for (int p = 2; p * p <= n; p++) {
        if (primes[p]) {
            for (int i = p * p; i <= n; i += p) {
                primes[i] = false;
            }
        }
    }
    std::cout << "Prime numbers up to " << n << " are: ";
    for (int i = 2; i <= n; i++) {
        if (primes[i])
            std::cout << i << " ";
    }
}
int main() {
    int limit;
    std::cout << "Enter a limit: ";
    std::cin >> limit;
    sieveOfEratosthenes(limit);
    return 0;
}