題目描述
因為 151 既是一個質數又是一個回文數（從左到右和從右到左是看一樣的），所以 151 是回文質數，
寫一個程式來找出范圍 [a,b] (5≤a<b≤100,000,000)( 一億)間的所有回文質數，
輸入格式
第 1 行: 二個整數 a 和 b .
5 500
輸出格式
5
7
11
101
131
151
181
191
313
353
373
383
說明與提示
Hint 1: Generate the palindromes and see if they are prime.
提示 1: 找出所有的回文數再判斷它們是不是質數（素數）.
Hint 2: Generate palindromes by combining digits properly. You might need more than one of the loops like below.
提示 2: 要產生正確的回文數，你可能需要幾個像下面這樣的回圈，
題目翻譯來自NOCOW，
思路：題目需要實作的功能非常簡單，但需要注意的是該題目有“高性能”的tag，這意味著在時間或空間方面有所要求，實作起來要注意優化，素數篩選可以使用歐拉線篩或埃式線篩，
Code：
#include <bits/stdc++.h>
#include <algorithm>
#define PI 3.141593
#define INF 0x3f3f3f3f
#define Best 0x7fffffff
#define _CRT_SECURE_NO_WARNINGS
using namespace std;
const int M = 2e8 + 5;
bool S(long long int num) {
if (num <= 3) {
return num > 1;
}
if (num % 6 != 1 && num % 6 != 5) {
return 0;
}
int b = (long long int)sqrt(num);
for (int i = 5; i <= b; i += 6) {
if (num % i == 0 || num % (i + 2) == 0) {
return 0;
}
}
return 1;
}
bool H(long long int num) {
long long int temp, sum = 0;
temp = num;
while (temp != 0) {
sum = sum * 10 + temp % 10;
temp = temp / 10;
}
if (sum == num && num > 0)
{
return 1;
}
else
{
return 0;
}
}
int main() {
long long int a[M], n = 0, s = 0, b, c;
cin >> b >> c;
for (long long int i = b; i <= c; i++) {
a[i] = i;
if (a[i] == 10000000)
break;
if (H(a[i]) == 1 && S(a[i]) == 1) {
n++;
cout << a[i] << endl;
}
}
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/143960.html
標籤：其他
下一篇：HDU-1716 排列2