In The End

个人博客

0%

素数筛

发表于 更新于 分类于 ，

今天这一篇是关于数论的知识，首先来写写素数筛

在有一些题目里，我们想快速分辨哪些数是素数，哪些数不是素数，我们有非常急切的渴望想建立一张素数表以便于我们查询哪些是素数那些不是，所以我们就有了这么一个算法——素数筛。

何为素数筛

前面已经解释地非常清楚了，就是把规定范围内所有的素数全部筛选出来。

O(nlogn)素数筛

首先我们介绍一个最基本的素数筛，O(nlogn)的复杂度的一个素数筛，原理非常简单，我们把所有的数先全部假定为素数，然后我们去找每个数的倍数，也就是比如我们找到了2，那么我们就去找4,6,8,10等等，把这些数全部排除出素数的范围内，这样一直递归到最远处就可以排除所有的非素数了，这样我们就找到了所有的素数。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
bool vaild[maxn];
void getPrime(int n){//n为范围，即1—n
    vaild[0]=vaild[1]= false;
    for(int i=2;i<=n;i++)
        vaild[i]=true;
    for(int i=2;i<=n;i++){
        if(vaild[i]){
            if(n/i<i)
                break;
            for(int j=i*i;j<=n;j+=i)
                vaild[i]=false;
        }
    }
}

线性素数筛

首先我们在介绍线性素数筛之前先思考一个问题：前面的普通素数筛会有什么缺点？

首先很明显有一个缺点就是会重复多次访问一个数字进行判断是否为素数，比如我们在i=2时会操作6，我们在i=3时依旧会访问6，这种时间的损耗我们可以想办法进行解决，也就有了这个线性素数筛。我们知道每个合数必有一个最小素因子。每个合数仅被它的最小素因子筛去正好一次，所以为线性时间。

那我们就可以枚举数字，然后记录素因子，ans数组中的素数是递增的,当i能整除ans[j]，那么i*ans[j+1]这个合数肯定被ans[j]乘以某个数筛掉，所以我们就不需要继续往下筛了，所以我们确保了每个数字只被它的最小素因子筛选，这样就不会有多余的操作了，复杂度自然也就下降到了O(n)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
bool vaild[maxn];
int ans[maxn];
void getPrime(int n){//n为范围，即1—n
    int tot=0;
    vaild[0]=vaild[1]= false;
    for(int i=2;i<=n;i++)
        vaild[i]=true;
    for(int i=2;i<=n;i++){
        if(vaild[i]) {
            tot++;
            ans[tot] = i;
        }
        for(int j=1;(j<=tot)&&(i*ans[j]<=n);j++){
            vaild[i*ans[j]]= false;
            if(i%ans[j]==0) break;
        }
    }
}

一到比较裸的素数筛题（POJ3048）

传送门：http://poj.org/problem?id=3048

主要思想就是去找最大的素数，所以我们只要每次输入进行判断最大素数即可，比较裸的题，有个小坑就是有一个数据是输入的1，所以代码中必须手动避开这个坑，我直接把num初始化为1就AC了

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
#include <iostream>
#define maxn 210000
using namespace std;

int vaild[maxn];
int ans[maxn];

void getPrime(int n){//n为范围，即1—n
    int tot=0;
    vaild[0]=vaild[1]= false;
    for(int i=2;i<=n;i++)
        vaild[i]=true;
    for(int i=2;i<=n;i++){
        if(vaild[i]) {
            tot++;
            ans[tot] = i;
        }
        for(int j=1;(j<=tot)&&(i*ans[j]<=n);j++){
            vaild[i*ans[j]]= false;
            if(i%ans[j]==0) break;
        }
    }
}

int main(){
    ios::sync_with_stdio(false);
    int n;ans[0]=1;
    getPrime(maxn);
    while(cin>>n){
        int a,mx=1,num=1;
        while(n--){
            cin>>a;
            for(int i=1;ans[i]<=a;i++){
                if(a%ans[i]==0&&mx<ans[i]){
                    mx=ans[i];
                    num=a;
                }
            }
        }
        cout << num << endl;
    }
    return 0;
}