acwing算法基础之数学知识--求小于等于n的所有质数

1 基础知识

核心思想：把2~n中的非质数打上标记（也即，筛掉），剩余的就是质数。

一般做法：

int primes[N]; //存储所有的质数
int st[N]; //存储是否被排除
int cnt;
int n;void f() {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;}}}//输出小于等于n的所有质数for (int i = 0; i < cnt; ++i) cout << primes[i] << " ";cout << endl;return;
}

线性筛选质数的方法，它的核心思想：非质数，只会被它的最小质因子筛掉。

int n, cnt;
int primes[N];
bool st[N];void f() {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; }}//输出所有质数for (int i = 0; i < cnt; ++i) cout << primes[i] << " ";cout << endl;return;
}

2 模板

暂无。。。

3 工程化

暂无。。。