练33.2 素数判断

解题思路

先排除小于2的数，再枚举因子 d 从2到√n，若有整除因子则不是质数；否则为质数。

正确性说明

若合数 n=ab，则两个因子中至少一个不大于√n；未找到这样的因子时，不存在非平凡因子，故为质数。

易错点

1 不是质数；d≤n/d 写法避免 d*d 溢出。

复杂度

时间 O(√n)，空间 O(1)。

参考代码（C++11）

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    long long n;
    cin >> n;
    bool prime = n >= 2;
    for (long long d = 2; d <= n / d && prime; d++)
        if (n % d == 0)
            prime = false;
    cout << (prime ? "Y" : "N") << "\n";
    return 0;
}