题解 | #判断一个数是不是质数#

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

bool is_prime(int n) {
    static vector<int> primes{2, 3, 5};
    if (n < 1)
        return false;
    if (n > primes.back()) {
        for (int i = primes.back() + 2; i <= n; i++) {
            bool is_prime = std::all_of(primes.begin(), primes.end(), [&](auto k) {
                return i % k != 0;
            });
            if (is_prime) {
            primes.push_back(i);
            }
        }
    }
    return std::find(primes.begin(), primes.end(), n) != primes.end(); // primes contain n
}


int main() {

    // write your code here......
    int n;
    cin >> n;
    cout << (is_prime(n) ? "是质数" : "不是质数");

    return 0;
}

使用 vector 进行缓存，如果遇到之前没遇到的质数，就依次 +2 往下查

如果数字特别特别大，那么这个方法不太行，需要使用预先计算某个范围内所有质数的策略。