BOJ - 1747 - 소수&팰린드롬
문제
문제 개념
문제
어떤 수와 그 수의 숫자 순서를 뒤집은 수가 일치하는 수를 팰린드롬이라 부른다. 예를 들어 79,197과 324,423 등이 팰린드롬 수이다.
어떤 수 N (1 ≤ N ≤ 1,000,000)이 주어졌을 때, N보다 크거나 같고, 소수이면서 팰린드롬인 수 중에서, 가장 작은 수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 N이 주어진다.
출력
첫째 줄에 조건을 만족하는 수를 출력한다.
구현
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
#include <iostream>
#include <cmath>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;
int main()
{
int num;
int answer;
cin >> num;
vector<bool> arr(10000001, 0);
arr[1] = true;
for(int i=2; i <= sqrt(10000000); i++)
{
if(!arr[i])
for(int j=i+i; j <= 10000000; j+=i)
arr[j] = true;
}
for(int i=0; i < 10000001; i++)
{
if(!arr[i] && i >= num)// 소수 이면서
{ // 문자열로 변환 후 revese시에도 같은수면
string temp = to_string(i);
reverse(temp.begin(), temp.end());
if(temp == to_string(i))
{
answer = i;
break;
}
}
}
cout << answer << endl;
return 0;
}
SOL
- 에라토스테네스의 체 알고리즘을 통해 10,000,000까지의 소수 추출 후
- 추출된 요소들 중 소수이면서 문자열로 변환 후 reverse시에도 같은 경우를 구함.