洛谷题单指南-暴力枚举-P1217 [USACO1.5] 回文质数 Prime Palindromes

原题链接：https://www.luogu.com.cn/problem/P1217

题意解读：

本题要找[a, b]范围内的所有回文质数，千万不要被题目提示所干扰，如果按照提示先产生各个长度的回文数，再依次判断是否是素数，程序写起来比较繁琐，需要根据a、b的长度，写8个判断是否产生1~8位回文数，最后做素数判断。

换一个思路，先用素数筛法筛出1~最大范围的素数，再去判断每个素数是否是回文数即可。

解题思路：

由于5≤a<b≤100,000,000，因此要筛出10⁸以内的素数，我们知道素数筛算法有三种（后面详解）：朴素筛、埃氏筛、线性筛，

朴素筛时间复杂度O(n*logn)，埃氏筛时间复杂度O(n*loglogn)，线性筛时间复杂度O(n)

对于10⁸数据量，只能用线性筛，而线性筛中涉及两个数组，一个用来保存所有素数，一个用来标记是否是合数，两个数组大小都要开到10⁸，内存限制125M，长度为10⁸的int数组占用空间约为400M，显然不够用。而且10⁸即使用线性筛也基本到了时间复杂度的极限，还要判断回文等操作，有可能超时。

对于回文数，有一个很重要的特定，如果这个数有偶数位，那么一定能被11整除，肯定不是素数，因此，数据最大范围虽然是10⁸，但是8位数肯定不是素数，所以数据最大范围可以缩小为10⁷。对于10⁷数据筛素数，埃氏筛、线性筛都能很好的胜任。

下面重点介绍几个关键知识点：

1、素数筛

所谓素数（质数），是指除了1和它本身以外不再有其他因数的自然数，一般用试除法判断素数（时间复杂度：O(sqrt(n))）：

bool isprime(int x)
{
    if(x <= 1) return false;
    for(int i = 2; i * i <= x; i++)
    {
        if(x % i == 0) return false;
    }
    return true;
}

注意：如果i比较大，i * i <= x有溢出风险，写成i <= x / i比较安全。

所谓素数筛，就是在一定范围内，筛出所有的素数。

例如要筛出1~n中所有的素数，如果枚举每一个数去判断是否是素数，时间复杂度为O(n*sqrt(n))，当n=10⁶都无法应对，因此出现了素数筛算法。

素数筛算法的核心思想是通过遍历2~n，将每个数的若干倍数都标记为合数，这样剩下的就都是素数，根据优化程度不同有三种算法：

a、朴素筛法：时间复杂度O(n*logn)

对于2~n中每一个数，如果没有标记成合数，则保存为素数，再将该数的2倍、3倍、4倍...标记为合数，代码如下：

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

const int N = 1e7;

int primes[N], cnt = 1; //保存筛出的素数
bool flag[N]; //标记合数

//朴素筛，筛出1 ~ N之间的素数，复杂度O(nlogn)
void getprimes1()
{
    for(int i = 2; i <= N; i++)
    {
        if(!flag[i]) primes[cnt++] = i; //如果i未被标记合数，则保存i为素数
        for(int j = i + i; j <= N; j += i) //把i的倍数都标记为合数
            flag[j] = true;
    }
}

int main()
{
    getprimes1(); 
    return 0;
}

b、埃氏筛法：时间复杂度O(n*loglogn)

由于在标记合数时，无论当前i时素数还是合数，都将其倍数进行了标记，这样必然导致大量重复标记。

例如：i=2时，i*4=8；而i=4时，又有i*2=8；8被重复标记

埃氏筛就是在朴素筛的基础上做出优化，只将素数的倍数进行标记，合数的倍数不标记，这样可以一定程度减少重复标记，代码如下：

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

const int N = 1e7;

int primes[N], cnt = 1; //保存筛出的素数
bool flag[N]; //标记合数

//埃氏筛，筛出1 ~ N之间的素数，复杂度O(nloglogn)
void getprimes2()
{
    for(int i = 2; i <= N; i++)
    {
        if(!flag[i]) //如果没有被标记为合数
        {
            primes[cnt++] = i; //保存素数
            for(int j = i + i; j <= N; j += i) //只对素数的倍数进行标记
                flag[j] = true;
        }
    }
}

int main()
{
    getprimes2(); 
    return 0;
}

c、线性筛法：时间复杂度O(n)

尽管埃氏筛只针对素数的倍数进行标记，但是还是会有一定程度的重复标记。

例如：i=2时，2*3=6；i=3时，i*2=6；6被重复标记。

线性筛在埃氏筛的基础上又进一步优化，使得每个合数只被它最小的素因子标记，这样每个合数都只被标记一次，如何做到呢？

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

const int N = 1e7;

int primes[N], cnt = 1; //保存筛出的素数
bool flag[N]; //标记合数

//线性筛，筛出1 ~ N之间的素数，复杂度O(n)
void getprimes3()
{
    for(int i = 2; i <= N; i++)
    {
        if(!flag[i]) primes[cnt++] = i; //如果i未标记为合数，则保存为素数
        for(int j = 1; j <= cnt; j++) //从小到大遍历每一个已保存的素数，要将i * primes[j]标记为合数
        {
            if(i * primes[j] > N) break; //超出最大值
            flag[i * primes[j]] = true; //将i * primes[j]标记为合数，primes[j]必然是i * primes[j]的最小素因子
            if(i % primes[j] == 0) break; //当i中包含一个primes[j]因子，就不能用此i去标记下一个数i * primes[j+1]，因为i * primes[j+1]包含因子primes[j]，而primes[j+1]不是最小素因子
        }
    }
}

int main()
{
    getprimes3(); 
    return 0;
}

此题任选埃氏筛或者线性筛算法都可以，由于埃氏筛更简单，这里采用埃氏筛。

2、判断回文数

只需要将数字进行翻转，比较翻转后的数字和原来的数字，如果相等则是回文数。

//判断x是否是回文数
bool ispalindrome(int x)
{
    int y = 0; //y是将x各个数字翻转后的数
    int t = x; //先将x复制一份
    while(t)
    {
        y = 10 * y + t % 10;
        t /= 10;
    }
    if(x == y) return true;
    else return false;
}

最后给出完整实现：

100分代码：

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

const int N = 1e7;

int primes[N], cnt = 1; //保存筛出的素数
bool flag[N]; //标记非素数
int a, b;

//埃氏筛，筛出1 ~ N之间的素数，复杂度O(nloglogn)
void getprimes2()
{
    for(int i = 2; i <= N; i++)
    {
        if(!flag[i]) //如果没有被标记为合数
        {
            primes[cnt++] = i; //保存素数
            for(int j = i + i; j <= N; j += i) //只对素数的倍数进行标记
                flag[j] = true;
        }
    }
}

//判断x是否是回文数
bool ispalindrome(int x)
{
    int y = 0; //y是将x各个数字翻转后的数
    int t = x; //先将x复制一份
    while(t)
    {
        y = 10 * y + t % 10;
        t /= 10;
    }
    if(x == y) return true;
    else return false;
}

int main()
{
    getprimes2(); //getprimes3();
    cin >> a >> b;

    for(int i = 1; i <= cnt; i++)
    {
        if(primes[i] >= a && primes[i] <= b && ispalindrome(primes[i]))
            cout << primes[i] << endl;
    }

    return 0;
}