python/C++专题课程/质数相关/IsPrime.cpp

#include <bits/stdc++.h>

using namespace std;

// 1、基本法 判断n是否为素数
bool is_prime(int n) {
    if (n < 2)
        return false;
    for (int i = 2; i < n; ++i)
        if (n % i == 0)
            return false;
    return true;
}

//2 、进阶优化方法
bool is_prime2(int n) {
    if (n < 2)
        return false;
    /**
     * 只需要判断到根号n即可，这里必须要使用小于等于符号
     * （不能仅仅使用小于符号，例如判断9）
     **/
    for (int i = 2; i * i <= n; ++i)
        if (n % i == 0)
            return false;
    return true;
}

int main() {
    for (int i = 2; i < 1000; i++) {
        cout << i << ":" << is_prime2(i) << endl;
    }
    return 0;
}