【题解】超级素数

佚名 6年前 (2019-04-20) 随笔 595人围观抢沙发百度已收录

题目描述

　　超级素数是指一个素数，每去掉后面一个数字，总能保证剩下的数为质数。例如：

　　373→37→3

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

　　这是一个长为3的超级素数。

输入格式

　　一个整数n（10≤n≤10^8）。

输出格式

　　从小到大输出所有小于等于n的超级素数，每个超级素数之间留一个空格。

输入样例

输出样例

2 3 5 7

题解

　　我们先从小的数开始搜索，搜出来的大的数相当于小的数末尾加上一个数字。容易想到，末尾这个数字不能是2,4,5,6,8，再想所有位的数字和不能为3的倍数，写好这两个剪枝就好了。

#include <iostream>
#include <cstdio>
#include <queue>

using namespace std;

int n;
int p[10005], cnt;
bool f[10005];
queue <int> q, c;
bool op;
const int b[4] = {1, 3, 7, 9};

bool isPrime(int x)
{
    for(register int i = 4; i <= cnt && p[i] * p[i] <= x; ++i)
    {
        if(x % p[i]) continue;
        return false;
    }
    return true;
}

int main()
{
    scanf("%d", &n);
    for(register int i = 2; i * i <= n; ++i)
    {
        if(f[i] ^ 1) p[++cnt] = i;
        for(register int j = 1; i * i * p[j] * p[j] <= n; ++j)
        {
            f[i * p[j]] = 1;
            if(!(i % p[j])) break;
        }
    }
    q.push(2);
    c.push(2);
    q.push(3);
    c.push(0);
    q.push(5);
    c.push(2);
    q.push(7);
    c.push(1);
    int now, tmp;
    while(1)
    {
        now = q.front();
        if(now > n) break;
        tmp = c.front();
        q.pop();
        c.pop();
        if(isPrime(now) ^ 1) continue;
        if(op) putchar(' ');
        else op = 1;
        printf("%d", now);
        for(register int i = 0; i < 4; ++i)
        {
            if(!((tmp + b[i]) % 3)) continue;
            q.push(now * 10 + b[i]);
            c.push((tmp + b[i]) % 3);
        }
    }
    return 0;
}