返回主页

线性筛（欧拉筛）

线性筛法，筛出 1 ~ N 中所有的质数，时间复杂度 O(N)

算法模板发布于 2026/08/23#质数#质数筛
C++19 行331 Bytes
下载文件
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5;
bool f[N+5];
int prime[N], cnt = 0;

int main() {
	
	f[0] = f[1] = 1;
	for (int i = 2; i <= N; i++) {
		if (!f[i]) prime[cnt++] = i;
		for (int j = 0; j < cnt && prime[j] * i <= N; j++) {
			f[prime[j] * i] = 1;
			if (i % prime[j] == 0) break;
		}
	}
	
	return 0;
}