原题链接: AcWing

题目描述:

“性感素数 ”是指形如 (p,p+6) 这样的一对素数。 之所以叫这个名字，是因为拉丁语管“六”叫“sex”（即英语的“性感”）。 现给定一个整数，请你判断其是否为一个性感素数。

输入格式

输入在一行中给出一个正整数 N。

输出格式

若 N 是一个性感素数，则在一行中输出 Yes，并在第二行输出与 N 配对的另一个性感素数（若这样的数不唯一，输出较小的那个）。 若 N 不是性感素数，则在一行中输出 No，然后在第二行输出大于 N 的最小性感素数。

数据范围

1≤N≤10^8

输入样例1：

47

输出样例1：

Yes
41

输入样例2：

21

输出样例2：

No
23

解题思路:

这道题是一个素数筛题，因为数据范围不大不小，所以用普通的暴力肯定会超时，那么我们可以利用素数的特性，判断一个数是不是素数，只需要判断n的根号前几个数即可。因为素数的特性是除了1和它本身之外不能被其它任何数整除， 如果一个数不是素数是合数，那么一定可以由两个自然数相乘得到，其中一个大于或等于它的平方根，一个小于或等于它的平方根。并且成对出现，所以只用计算到该数的平方根以下看除了1有没有该数的因数，若没有，则是素数。

代码:

#include <iostream>
#include <cmath>
using namespace std;
int fun(int n)
{
    if(n<=1)
    {
        return 0;
    }
    for(int i=2;i<=n/i;i++) //这里for循环的终止条件利用了试除法，也可以改为i<=sqrt(n);直接求根号
    {
        if(n%i==0)
        {
            return 0;
        }
    }
    return 1;
}
int main()
{
    int n;
    scanf("%d",&n);
    if(fun(n)&&(fun(n-6)||fun(n+6)))
    {
        printf("Yes\n");
        if(fun(n-6))
        {
            printf("%d",n-6);
        }else{
            printf("%d",n+6);
        }
    }else{
        printf("No\n");
        int i=n+1;
        while(1)
        {
            if(fun(i)&&(fun(i+6)||fun(i-6)))
            {
               printf("%d",i);
               break;
            }
            i++;
        }
    }
    return 0;
}

除了上面的方法外，素数判断还有其他更快的方法：

这里引入一个经典的题目：

原题链接

题目描述:

给定一个正整数 n，请你求出 1∼n 中素数的个数。

数据范围

1≤n≤10^6

普通筛法：O(nlogn)

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e6+1;
int q[N],ans,n;
bool st[N];
void fun()
{
    for(int i=2;i<=n;i++)
    {
        if(!st[i])
        {
            q[ans++]=i;//把素数存起来
            for(int j=i;j<=n;j+=i) //不管是合数还是质数，都用来筛掉后面它的倍数
            {
                st[j]=true; //可以用质数就把所有的合数都筛掉；
            }
        }
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin>>n;
    fun();
    cout<<ans<<endl;
    return 0;
}

埃氏筛法：O(nloglogn)

void get_primes1(){
    for(int i=2;i<=n;i++){
        if(!st[i]){
            primes[cnt++]=i;
            for(int j=i;j<=n;j+=i) st[j]=true;//可以用质数就把所有的合数都筛掉；
        }
    }
}

线性筛法： O(n)

void get_primes(){
    //外层从2~n迭代，因为这毕竟算的是1~n中质数的个数，而不是某个数是不是质数的判定
    for(int i=2;i<=n;i++){
        if(!st[i]) primes[cnt++]=i;
        for(int j=0;primes[j]<=n/i;j++){//primes[j]<=n/i:变形一下得到——primes[j]*i<=n,把大于n的合数都筛了就
        //没啥意义了
            st[primes[j]*i]=true;//用最小质因子去筛合数

            //1)当i%primes[j]!=0时,说明此时遍历到的primes[j]不是i的质因子，那么只可能是此时的primes[j]<i的
            //最小质因子,所以primes[j]*i的最小质因子就是primes[j];
            //2)当有i%primes[j]==0时,说明i的最小质因子是primes[j],因此primes[j]*i的最小质因子也就应该是
            //prime[j]，之后接着用st[primes[j+1]*i]=true去筛合数时，就不是用最小质因子去更新了,因为i有最小
            //质因子primes[j]<primes[j+1],此时的primes[j+1]不是primes[j+1]*i的最小质因子，此时就应该
            //退出循环，避免之后重复进行筛选。
            if(i%primes[j]==0) break;
        }
    }

}