线性筛

发表于 | 分类于

线性筛

模板

线性筛是在埃氏筛的基础上保证每个质数只会被它的最小质因数筛一次的筛法，可以将时间复杂度优化到\(O(n)\)。

对于数\(i\)，从小到大枚举\(prime\)数组（已经筛出的质数数组），当第一次出现\(prime[j] \mid i\) 时，可知\(prime[j]\)是\(i\times prime[j]\)的最小质因数，而对于\(i \times prime[j+1]\)，它的最小质因数是\(prime[j]\)，此时为了保证只被最小质因数筛掉，停止枚举。

对于合数\(x\)，设它的最大质因数为\(x_0\)，在枚举到\(\frac{x}{x_0}\)时一定会被筛掉，则所有的合数都能够被筛掉。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
const int N = 100010;
int prime[N],n,now;
bool isprime[N];
void get_prime()
{
    for(int i = 2;i <= n;i++)
    {
        if(!isprime[i])
        now++,prime[now] = i;//如果没有被筛掉，就是质数
        for(int j = 1;j <= now && i * prime[j] <= n;j++)
        {
            isprime[i * prime[j]] = 1;
            if(i % prime[j] == 0)
            break;//保证每个合数只会被它的最小质因数筛掉
        }
    }
}

例题

acwing196 质数距离

题目链接：https://www.acwing.com/problem/content/198/

题意

给定两个正整数\(L,U\)，在闭区间\([L,U]\)中找到距离最近和最远的相邻质数。

数据范围

\(1 \leq L<U\leq 2^{31}-1,U-L\leq 10^{6}\)

题解

可以考虑求出\(L\)到\(U\)区间内的全部质数，但\(L\)和\(U\)本身数据范围较大，线性筛无法做到。

考虑使用二次筛法，对于合数\(X\)，由于\(X\)必然存在一个不大于\(\sqrt{X}\)的质数因子，于是先用线性筛筛出所有小于\(10^{5}\)的质数，分别对这些质数标记它们的倍数中在\([L,U]\)的，剩下没有被标记过的就是所有的质数。

最后由于线性查找其中相邻两个质数中差最大和最小的即可，时间复杂度\(O(U-L)\)

代码 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include<iostream>
#include<vector>
#include<cstring>
using namespace std;
const int N = 100010;
long long prime[N],l,r,now;
bool isprime[N],isans[N * 10];
vector<long long> v;
void get_prime()
{
    for(int i = 2;i <= N;i++)
    {
        if(!isprime[i])
        now++,prime[now] = i;
        for(int j = 1;j <= now && i * prime[j] <= N;j++)
        {
            isprime[i * prime[j]] = 1;
            if(i % prime[j] == 0)
            break;
        }
    }
}
void get_ans()
{
    memset(isans,0,sizeof(isans));
    for(int i = 1;i <= now;i++)
    {
        long long ll = l / prime[i] * prime[i];
        while(ll <= r)
        {
            if(ll >= l && ll != prime[i])
            isans[ll - l] = 1;
            ll += prime[i];
        }
    }
}
int main()
{
    get_prime();
    while(cin >> l >> r)
    {
        if(l == 1)
        l = 2;
        get_ans();
        v.clear();
        for(int i = 0;i <= r - l;i++)
        {
            if(!isans[i])
            v.push_back(i + l);
        }
        if(v.size() <= 1)
        printf("There are no adjacent primes.\n");
        else
        {
            long long minn = 1e6,maxn = 0,l1,r1,l2,r2;
            for(int i = 1;i < v.size();i++)
            {
                if(v[i] - v[i - 1] < minn)
                l1 = v[i - 1],r1 = v[i],minn = v[i] - v[i - 1];
                if(v[i] - v[i - 1] > maxn)
                l2 = v[i - 1],r2 = v[i],maxn = v[i] - v[i - 1];
            }
            printf("%lld,%lld are closest, %lld,%lld are most distant.\n",l1,r1,l2,r2);
        }
    }
    system("pause");
    return 0;
}