✍

WerChange

广东中山一只现役 OIer

数论

质数及其筛法

质数

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

普通筛法

过程

枚举 $[2,n-1]$，如果 $n$ 在这个范围内有因子，则 $n$ 不是因数。
因为 $n$ 的因子成对出现，所以我们可以枚举 $[2,\sqrt{n}]$。

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


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)$。