//朴素版的筛素数 O(nlogn)
void get_primes1(int n) {
for(int i = 2; i <= n; i++) {//每个i都要处理
if(!st[i]) prime[cnt++] = i;//false是质数,true是合数
for(int j = i+i; j <= n; j += i)//倍增法,加i的加,每个数都是
st[j] = true;
}
}
//埃式筛法 O(nloglogn)
void get_primes2(int n) {
for(int i = 2; i <= n; i++) {//每个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++) {//也就是小于sqrt,i从0开始计数
//对于任意一个合数x,假设pj为x最小质因子,当i<x/pj时,一定会被筛掉
st[prime[j]*i] = true;//倍数
if(i % prime[j] == 0) break;//继续扩大,说明i是prime[j]的倍数了,找下个质数进行倍增,i%pj == 0, pj定为i最小质因子,pj也定为pj*i最小质因子
/*
1.i%pj == 0, pj定为i最小质因子,pj也定为pj*i最小质因子
2.i%pj != 0, pj定小于i的所有质因子,所以pj也为pj*i最小质因子
*/
}
}
}
//比较快的判断素数的方法
bool ispri(int k) {
if(k <= 1) return false;
if(k <= 3) return true;
if(k % 6 != 1 && k % 6 != 5) return false;
for(int i = 5;i < k / i;i += 6) {
if(k % i == 0 || k % (i + 2) == 0) return false;
}
return true;
}