判断是否为质数

O(n)

bool isPrime(int n) {
    for (int i = 2; i <= n; ++ i) // ++ i 性能优于 i ++
        if (n % i == 0) return false;
    return true;
}

O(sqrt(n))

bool isPrime(int n) {
    for (int i = 2; i * i <= n; ++ i) // sqrt(n)
        if (n % i == 0) return false;
    return true;
}

筛质数

O(nlogn)

void get_prime(int n) {
    for (int i = 2; i <= n; ++ i) {
        if (!st[i]) prime[cnt ++] = i; // 存质数
        for (int j = i; j <= n; j += i) // 无论质数还是合数，筛掉它的倍数
            st[i] = true;
    }
}

O(nloglogn)

void get_prime(int n) {
    for (int i = 2; i <= n; ++ i) {
        if (!st[i]) {
            prime[cnt ++] = i;
            for (int j = i; j <= n; j += i) // 用质数筛掉合数
                st[j] = true;
        }
    }
}

线性筛法 O(n)

void get_prime(int n) {
    for (int i = 2; i <= n; ++ i) {
        if (!st[i]) prime[cnt ++] = i;
        for (int j = 0; prime[j] <= n / i; j ++) {
            st[prime[j] * i] = true;
            if (i % prime[j] == 0) break; // prime[j]是i的最小质因子，也是prime[j] * i的最小质因子
            // prime[j + 1]就不是prime[j + 1] * i的最小质因子，退出循环，避免之后重复筛选
        }
    }
}