试除法求质数

**这里推荐写i <= x / i，防止爆int```

1
2
3
4
5
6
bool is_prime(int x) {
    if(x < 2) return false;
    for(int i = 2; (LL)i * i <= x; ++ i)
        if(x % i == 0) return false;
    return true;
}

质数筛

埃式筛

O(nlog(logn))

筛掉所有质数的倍数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int primes[N],cnt;

int n;

bool st[N];

void get_primes(){
    for(int i = 2; i <= n; ++ i) 
        if(!st[i]) {
            primes[cnt ++] = i;
            for(int j = i + i; j <= n; j += i)
                st[j] = true;
        }
}

线性筛

将所有合数通过其最小质因子筛掉。

1
2
3
4
5
6
7
8
9
void get_primes(){
    for(int i = 2; i <= n; ++ i) {
        if(!st[i]) primes[cnt ++] = i;
        for(int j = 0; primes[j] <= n / i; ++ j) {
            st[primes[j] * i] = true;
            if(i % primes[j] == 0) break; 
        }
    }
}