Warning: session_start(): open(/tmp/sess_543e34635c54369eea7ff50d564b40e6, O_RDWR) failed: No space left on device (28) in /data/wiki/inc/init.php on line 239
Warning: session_start(): Failed to read session data: files (path: ) in /data/wiki/inc/init.php on line 239
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/auth.php on line 430
Writing /data/wiki/data/cache/d/d8bb799d01e07e83e070675a3db69567.captchaip failed
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103
Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/Action/Export.php on line 103
====== 筛法 ======
确定素数。
===== 埃氏筛 =====
==== 思想 ====
从每个素数出发，将其倍数都筛掉。
==== 性能 ====
每一个合数会被访问多次；复杂度$O(nloglogn)$。
==== 代码 ====
for(int i=2;i<=maxn;i++)
{
if(!vist[i])
for(int j=i*i;j<=maxn;j+=i)
vist[j]=1;
}
===== 线性筛（欧拉筛）=====
==== 思想 ====
对于每一个i，寻找素数使得与i的乘积中该素数为最小因子。由于每一个数的最小因子一定，该数就被唯一地访问。
==== 性能 ====
避免了重复访问；复杂度$O(n)$（？）。
==== 代码 ====
for(int i=2;i<=maxn;i++)
{
if(!vist[i])
prime[++t]=i;
for(int j=1;j<=t&&i*prime[j]<=maxn;j++)
{
vist[i*prime[j]]=1;
if(!(i%prime[j]))
break;
}
}
杜教筛、min_25筛、洲阁筛学到积性函数再补。