筛法

质数

质数，又称素数。如果一个数\(a \in \N^+（a\neq 1）\)的因子有且仅有\(1\)和它本身，则称数\(a\)为质数。

普通筛法

过程

1. 枚举\([2,n-1]\)，如果\(n\)在这个范围内有因子，则\(n\)不是因数。
2. 因为\(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})\)，因为太慢了，所以有以下两种更快的筛法。

埃式筛法

过程

1. 循环从\(2\)~\(n\)，判断当前的下标\(i\)是否曾经被确认为合数。
2. 如果\(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)\)。

欧拉筛法

过程

1. 循环从\(2\)~\(n\)，判断当前的下标\(i\)是否曾经被确认为合数。
2. 如果\(i\)不是合数，把质数\(i\)放进质数的集合里。
3. 无论\(i\)是不是合数，都遍历一遍质数集合，并将集合中遍历到的当前元素\(p_j\)乘以\(i\)后标记为合数，直至\(p_j\times i >n\)。
4. 执行步骤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)\)。