题解 P1218 【[USACO1.5]特殊的质数肋骨 Superprime Rib】

Sino_E · 2017-10-28 23:23:09 · 题解

题目要我们求长度为n的特殊质数。

首先长度为n的特殊质数肯定建立在长度为n-1的特殊质数上才符合条件。

于是我们先求出长度为1的质数，再在这个质数上枚举加上0~9的数字，判断是不是质数，以此来得到长度为2的特殊质数。

以此类推，可以得到长度为3的、长度为4的、一直到n。

循环枚举模拟，暴力判断是否为质数即可。

复杂度讲道理是不高的。因为从长度为1开始这种质数就很少嘛。

其它的质数判断就不多讲啦~

下面是代码。

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

const int N=1e5;
int pri[N],p;   //现有的质数
int npri[N],np; //新处理的质数    
inline bool ispri(int x){
    if(x==0||x==1) return false;
    for(int i=2;i*i<=x;i++)
        if(x%i==0) return false;
    return true;
}   //暴力判断是否为质数

int main(){
    int n;
    cin>>n;
    p=1;    //初始化时长度为0，即由数字0推得长度为1的特殊质数
    for(int i=1;i<=n;i++){
        np=0;
        for(int j=0;j<p;j++)
            for(int k=0;k<=9;k++)   //枚举质数和新加上的数字
                if(ispri(pri[j]*10+k))npri[np++]=pri[j]*10+k;   //若i-1长度的质数加上了该数字仍是质数，则放入新的i长度的质数数组当中。
        memcpy(pri,npri,sizeof(npri));  //复制数组
        p=np;
    }
    for(int i=0;i<p;i++) printf("%d\n",pri[i]);
    return 0;
}