洛谷 回文质数
内容纲要

[USACO1.5] 回文质数 Prime Palindromes

题目描述

因为 151 既是一个质数又是一个回文数(从左到右和从右到左是看一样的),所以 151 是回文质数。

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

输入格式

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

输出格式

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

样例 #1

样例输入 #1

5 500

样例输出 #1

5
7
11
101
131
151
181
191
313
353
373
383
#include <bits/stdc++.h>
using namespace std;

int a, b;
// 埃氏筛法
void prime(vector<int> &isprime)
{
    //i <= b / i是因为i*i之后的数已经被筛掉了
    for (int i = 2; i <= b / i; i++)
    {
        if (isprime[i])
        {
            // 从i*i开始是因为i*2,i*3...i*(i-1)在之前已经被筛掉了
            for (int j = i * i; j <= b; j += i)
                isprime[j] = 0;
        }
    }
}
// 判断是否是回文数
bool isHWS(int x)
{
    int temp = x, ans = 0;
    while (temp != 0)
    {
        ans = ans * 10 + temp % 10;
        temp /= 10;
    }
    return ans == x;
}

int main()
{
    cin >> a >> b;
    /*除了11以外,一个数的位数是偶数的话,不可能为回文数素数。
    证明:
    如果一个回文素数的位数是偶数,则它的奇数位上的数字和与偶数位上的数字和必然相等;
    根据数的整除性理论,容易判断这样的数肯定能被11整除,所以它就不可能是素数 */
    if (b > 10000000)//一千万到一亿是八位数,不可能是回文数素数
        b = 9999999;
    vector<int> isprime(b + 1, 1);
    prime(isprime);//标记素数
    if (a > b)
        return 0;
    if (a % 2 == 0)//如果a是偶数,那么a+1是奇数,所以a+1是第一个要判断的数
        a++;
    for (int i = a; i <= b; i += 2)//只判断奇数
    {
        if (isprime[i] && isHWS(i))
            cout << i << endl;
    }
    return 0;
}
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇