质数回文

[USACO1.5] 回文质数 Prime Palindromes

题目描述

因为151既是一个质数又是一个回文数（从左到右和从右到左是看一样的），所以151是回文质数。

写一个程序来找出范围[a,b] (5 \le a < b \le 100,000,000)(一亿)间的所有回文质数。

输入格式

第一行输入两个正整数a和b。

输出格式

输出一个回文质数的列表，一行一个。

样例 #1

样例输入 #1

1
5 500

样例输出 #1

1
2
3
4
5
6
7
8
9
10
11
12
5
7
11
101
131
151
181
191
313
353
373
383

题目分析

因为回文数比较少,可以先找出回文数,再筛选素数
回文数利用模除和除来进行判断
素数:偶数不会有素数,位数为偶数的除了11都不是质数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include <iostream>
#include <cmath>
using namespace std;

bool isPalindrome(int x){
    int a[15] = {0};
    int flag = 0;
    while(x > 0){
        a[flag] = x % 10;
        x /= 10;
        flag++;
    }
    for(int i = 0; i < flag / 2; i++){
        if(a[i] != a[flag - i - 1])
            return false;
    }
    return true;
}

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

bool isValidRange(int x){
    if((1000 <= x && x <= 9999) || (100000 <= x && x <= 999999))
        return false;
    return true;
}

int main(){
    int l, r;
    cin >> l >> r;
    if(l == 2) 
        cout << "2" << endl;
    if(l % 2 == 0) 
        l++;
    r = min(9999999, r);
    for(int i = l; i <= r; i += 2){
        if(!isValidRange(i))
            continue;
        if(!isPalindrome(i))
            continue;
        if(!isPrime(i))
            continue; 
        cout << i << endl;
    }
    return 0;
}

素数还可以使用埃氏筛法,欧拉筛法进行筛选

埃氏筛法

埃氏筛法的思想就是：先去掉2的倍数，再去掉3的倍数，再去掉4的倍数，……依此类推，直到最大数小于最后一个标出的素数的平方，那么剩下的序列中所有的数都是素数。 时间复杂度：O(nloglogn)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include<bits/stdc++.h>
#define maxn 10000000
#define INF 0x3f3f3f3f
using namespace std;
bool a[maxn+5];
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    memset(a,true,sizeof(a));
    for(int i=2;i<=n;i++){
        if(a[i]){
            for(int j=2;i*j<=n;j++)
                a[i*j]=false;
        }
    }
    a[1]=false;
    int t;
    while(m--)
    {
        scanf("%d",&t);
        if(a[t])printf("Yes\n");
        else printf("No\n");
    }
    return 0;
}

欧拉筛法

 核心原理：对于每个合数，都只由它最小的质因子筛掉。
 比如：（假定：ans[]数组中存放着已经确定的素数）合数 i = p（最小素因子）* a;  若 i%ans[j] ==0;
 则 i * ans[j+1] =  p * a * ans[j+1] 可以被后面的 a * ans[j+1] 再乘以素数 p 筛选出来，
 (显而p<ans[j+1]所以i%ans[j] == 0 时要停止)

https://www.bilibili.com/video/BV1LR4y1Z7pm讲解视频

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include<bits/stdc++.h>
#define maxn 10000000
#define INF 0x3f3f3f3f
using namespace std;
bool a[maxn+5];
int b[maxn+5];//存储质数
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    memset(a,true,sizeof(a));
    a[1]=false;
    int k=1;
    for(int i=2;i<=n;i++){
        if(a[i])   //如果i为质数
            b[k++]=i;//存上
        for(int j=1;j<=k&&i*b[j]<=n;j++){
            a[i*b[j]]=false;
            if(i%b[j]==0)break;
        }
    }
    int t;
    while(m--){
        scanf("%d",&t);
        if(a[t])printf("Yes\n");
        else printf("No\n");
    }
    return 0;
}