蓝桥 3205.小明的素数对（内含试除法，埃氏筛，欧拉筛代码）

目录

题目

题目解读

思路

代码

注

总结

试除法

埃氏筛

欧拉筛

题目

题目解读

题目意思很简单，就是输入一个树n，然后求1-n里的素数，然后求这些素数里满足他们两两之差也是素数的对数有多少对。

思路

思路很简单，可直接利用埃式筛选法筛（或利用欧式筛法）筛选出1-n里的素数有什么，然后求他们两两之差可利用试除法判断他们是不是素数，是的话，利用计数器自增，而后即可求出答案。

代码

#include<bits/stdc++.h>
using namespace std;

const int MAXN = 1e7;                 //定义空间大小，1e7约10M
int prime[MAXN+1];                    //存放素数，它记录visit[i] = false的项
bool visit[MAXN+1];                   //true表示被筛掉，不是素数
int E_sieve(int n)                    //埃式筛法，计算[2, n]内的素数
{                 
    int k=0;                            //统计素数个数
    for(int i=0; i<=n; i++)  visit[i]= false;  //初始化
    for(int i=2; i<=n; i++)            //从第一个素数2开始。
    {        
        if(!visit[i])
        {
            prime[k++] = i;               //i是素数，存储到prime[]中
            for(int j=2*i; j<=n; j+=i)  //i的倍数，都不是素数。
                visit[j] = true;          //标记为非素数，筛掉
        }
    }
    return k;                              //返回素数个数
}

bool is_prime(int n)//试除法
{
    if(n<=1)
        return false;
    for(int i=2;i*i<=n;i++)
        if(n%i==0)return false;// 如果 n 能被 i 整除，不是素数
    return true;//是素数
}

int main()
{
    int num;
    cin >> num;
    int cnt=0;// 计数器，记录满足条件的素数对个数
    int n=E_sieve(num);// 调用埃氏筛法，计算 [2, num] 范围内的素数，并返回素数个数

    // 枚举所有素数对 (prime[i], prime[j-1])，其中 i > j-1
    for(int i=1;i<n;i++)
    {
        for(int j=i;j>0;j--)
        {
            int diff=prime[i]-prime[j-1];// 计算素数之间的差值
            if(is_prime(diff))// 如果差值也是素数
                cnt++;//计数器加一
        }
    }
    cout << cnt;
    return 0;
}

注

main函数里for循环这段不要为了方便写成下面这样。不要直接把埃氏筛法作为条件插入到for里，这样每次for循环都得调用一次埃氏筛法，会导致运行超时。（我就是这样 懒得多写一行 已经吸取教训了