Appearance
若无特殊说明,本章涉及的变量皆为正整数。
定义
- 若
只能被 和 整除,则 是质数,否则是合数; : 以内的质数个数, ; :第 个质数, 。
质数判定
若
时间复杂度:
cpp
bool isPrime(int n) {
if (n < 2)
return false;
for (int i = 2; i <= sqrt(n); i ++)
if (n % i == 0)
return false;
return true;
}
质数筛法
求
暴力算法
对
cpp
vector<int> prime;
bool isPrime(int n) {
if(n < 2) return false;
for(int i = 2; i <= sqrt(n); i ++)
if(n % i == 0) return false;
return true;
}
void getPrime(int n) {
for(int i = 2; i <= n; i ++)
if(isPrime(i))
prime.push_back(i);
}
埃氏筛法
任意数的倍数必定是合数。
划掉
- 划掉
的倍数: ; - 划掉
的倍数: ; 已划,则 的倍数也已划,跳过; - 划掉
的倍数: ; 已划,跳过;
时间复杂度:
埃氏筛法优化:
时间复杂度:
cpp
const int N = 1e6;
bool mark[N]; // mark[i]: i 是否被划掉
vector<int> p;
void getPrime(int n) {
for (int i = 2; i <= n; i ++) {
if (mark[i])
continue;
p.push_back(i);
for (int v = i * i; v <= n; v += i)
mark[v] = true;
}
}
线性筛法
埃氏筛法 中,有些数会被重复划,如
使每个合数只被其最小质因子划去。
在第
cpp
for (int v = i * i; v <= n; v += i) {
mark[v] = true;
}
而线性筛法划掉的是
cpp
for (int j = 0; j < p.size() && i * p[j] <= n; j ++) {
if (/* i × p[j] 的最小质因子是 p[j] */) {
mark[i * p[j]] = true;
}
}
对于任意
现在只需讨论 if()
的条件。举个例子:
,最小质因子是 ,可以划; ,最小质因子是 ,可以划; ,最小质因子是 ,跳过; ,最小质因子是 ,跳过; ,最小质因子是 ,跳过;
不难发现,由于
cpp
for (int j = 0; j < p.size() && i * p[j] <= n; j ++) {
mark[i * p[j]] = true;
if (i % p[j] == 0)
break;
}
时间复杂度:
cpp
const int N = 1e6;
bool mark[N];
vector<int> p;
void getPrime(int n) {
for (int i = 2; i <= n; i ++) {
if (!mark[i])
p.push_back(i);
for (int j = 0; j < p.size() && i * p[j] <= n; j ++) {
mark[i * p[j]] = true;
if (i % p[j] == 0)
break;
}
}
}