33DAI：/* 线性筛/欧拉筛 */

2026-02-26T03:04:48Z

线性筛/欧拉筛

←上一版本		2026年2月26日 (四) 03:04的版本
第60行：		第60行：
	{		{
	// i*pri[j]		// i*pri[j]
	if (i * pri[j] > n)		if (1LL * i * pri[j] > n)
	break;		break;
	p[i * pri[j]] = false;		p[i * pri[j]] = false;

33DAI：创建页面，内容为“==判断单个质数== $O(\sqrt{x})$ bool is_prime(long long x) { if (x < 2) return false; for (long long i = 2; i * i <= x; i++) if (x % i == 0) return false; return true; } ==筛法== ===埃氏筛=== $O(n\log \log n)$ const int MAXN = 10'000'000; bool p[MAXN + 1]; //筛出 1~n 中的每个数是否为质数…”

2026-02-12T08:55:11Z

创建页面，内容为“==判断单个质数== <math>O(\sqrt{x})</math> <syntaxhighlight lang="cpp" line> bool is_prime(long long x) { if (x < 2) return false; for (long long i = 2; i * i <= x; i++) if (x % i == 0) return false; return true; } </syntaxhighlight> ==筛法== ===埃氏筛=== <math>O(n\log \log n)</math> <syntaxhighlight lang="cpp" line> const int MAXN = 10'000'000; bool p[MAXN + 1]; //筛出 1~n 中的每个数是否为质数…”

新页面

==判断单个质数==

<math>O(\sqrt{x})</math>

<syntaxhighlight lang="cpp" line>
bool is_prime(long long x)
{
if (x < 2)
return false;
for (long long i = 2; i * i <= x; i++)
if (x % i == 0)
return false;
return true;
}
</syntaxhighlight>

==筛法==

===埃氏筛===

<math>O(n\log \log n)</math>

<syntaxhighlight lang="cpp" line>
const int MAXN = 10'000'000;
bool p[MAXN + 1];
//筛出 1~n 中的每个数是否为质数
void get_primes(int n)
{
//初始化
p[0] = p[1] = false;
for (int i = 2; i <= n; i++)
p[i] = true;
//筛
for (int i = 2; i <= n; i++)
if (p[i])
for (int j = i + i; j <= n; j += i)
p[j] = false;
}
</syntaxhighlight>

===线性筛/欧拉筛===

<math>O(n)</math>

<syntaxhighlight lang="cpp" line>
const int MAXN = 10'000'000;
bool p[MAXN + 1];
vector<int> pri;
// 筛出 1~n 中的每个数是否为质数
void get_primes(int n)
{
for (int i = 1; i <= n; i++)
p[i] = true;
p[0] = p[1] = false;
for (int i = 2; i <= n; i++)
{
if (p[i])
pri.push_back(i);
for (int j = 0; j < pri.size(); j++)
{
// i*pri[j]
if (i * pri[j] > n)
break;
p[i * pri[j]] = false;
if (i % pri[j] == 0)
break;
}
}
}
</syntaxhighlight>

质数判断 - 版本历史

33DAI：​/* 线性筛/欧拉筛 */

33DAI：/* 线性筛/欧拉筛 */