判断素数

数学

试除法

就是从2开始一个一个试，只要都无法除尽即为素数。需要注意的是只要试到 $\sqrt{x}$ 即可。

#include <iostream>
 
using namespace std;
 
bool is_prime(int x) {
    if (x < 2) return false;
    for (int i = 2; i <= x / i; i ++ ) {
        if (x % i == 0) return false;
    }
    return true;
}
 
int main() {
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i ++ ) {
        int a;
        scanf("%d", &a);
        printf("%s\n", is_prime(a) ? "Yes" : "No");
    }
    
    return 0;
}

埃拉托斯特尼筛法（Sieve of Eratosthenes）

埃拉托斯特尼筛法（Sieve of Eratosthenes） 是一种高效找出一定范围内所有素数的算法。
原理简单：

1. 先假设所有数都是素数
2. 从 2 开始，把它的倍数都标记为“合数”
3. 找到下一个没被标记的数（下一个素数），再把它的倍数标记
4. 重复直到 $\sqrt{n}$。

#include <iostream>
#include <vector>
 
using namespace std;
 
void sieve(int n, vector<bool>& primes) {
    primes[0] = primes[1] = false;
    
    for (int i = 2; i * i <= n; i ++ ) {
        if (primes[i]) {
            for (int j = i * i; j <= n; j += i) {
                primes[j] = false;
            }
        }
    }
}
 
int main() {
    int n;
    scanf("%d", &n);
    vector<bool> p(n + 1, true);
    sieve(n, p);
    
    int ans = 0;
    for (int i = 2; i <= n; i ++ ) {
        if (p[i]) ans ++;
    }
    printf("%d\n", ans);
    
    return 0;
}