筛法
质数
质数，又称素数。如果一个数\(a \in \N^+（a\neq 1）\)的因子有且仅有\(1\)和它本身，则称数\(a\)为质数。
普通筛法
过程
- 枚举\([2,n-1]\)，如果\(n\)在这个范围内有因子，则\(n\)不是因数。
- 因为\(n\)的因子成对出现，所以我们可以枚举\([2,\sqrt{n}]\)。
Code
bool isprime(int n)
{
for(int i=2;i*i<=n;i++)
if(n%i==0)
return 0;
return 1;
}
int main()
{
scanf("%d",&n);
for(int i=2;i<=n;i++) //将i=1排除掉。
if(isprime(i))
printf("%d\n",i);
return 0;
}
时间复杂度
时间复杂度为\(\Omicron(N\sqrt{N})\)，因为太慢了，所以有以下两种更快的筛法。
埃式筛法
过程
- 循环从\(2\)~\(n\)，判断当前的下标\(i\)是否曾经被确认为合数。
- 如果\(i\)不是合数，那么将质数\(i\)放进质数集合里并不断成倍增加，再将增加所得的数标记为合数，直至大于\(n\)为止。如果\(i\)为合数，重复找下一个\(i\)。
Code
void getprime(int n)
{
for(int i=2;i<=n;i++)
{
if(flgs[i]==1) // flgs[i]表示i是否为合数
continue;
primes[++cnt]=i; // primes[]表示质数集合
for(int j=i;j<=n/i;j++)
flgs[j*i]=1;
}
}
时间复杂度
时间复杂度为\(\Omicron(N \log N)\)。
欧拉筛法
过程
- 循环从\(2\)~\(n\)，判断当前的下标\(i\)是否曾经被确认为合数。
- 如果\(i\)不是合数，把质数\(i\)放进质数的集合里。
- 无论\(i\)是不是合数，都遍历一遍质数集合，并将集合中遍历到的当前元素\(p_j\)乘以\(i\)后标记为合数，直至\(p_j\times i >n\)。
- 执行步骤3时，如果\(p_j\mid i\)，先将\(p_j\times i\)标记为合数，再重新找下一个\(i\)。
Code
void getprime(int n)
{
for(int i=2;i<=n;i++)
{
if(flgs[i]==0)
primes[++cnt]=i;
for(int j=1;j<=cnt;j++)
{
if(primes[j]*i>n)
break;
flgs[primes[j]*i]=1;
if(i%primes[j]==0)
break;
}
}
}
时间复杂度
时间复杂度为\(\Omicron(N)\)。