소수&팰린드롬
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞은 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 256 MB | 5009 | 1134 | 828 | 23.684% |
문제
어떤 수와 그 수의 숫자 순서를 뒤집은 수가 일치하는 수를 팰린드롬이라 부른다. 예를 들어 79,197과 324,423 등이 팰린드롬 수이다.
어떤 수 N (1 ≤ N ≤ 1,000,000)이 주어졌을 때, N보다 크거나 같고, 소수이면서 팰린드롬인 수 중에서, 가장 작은 수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 N이 주어진다.
출력
첫째 줄에 조건을 만족하는 수를 출력한다.
예제 입력 1
1
31
예제 출력 1
1
101
풀이
팰린드롬 계산하는 것을 문자열로 바꿔서 풀었는데,
1
2
3
4
5
6
7
8
bool pldr(int num){
int a=0, b=num
while(b!=0){
a= a*10 + b%10;
b= b/10;
}
return a==num;
}
으로 풀 수 있다는 것을 배웠다.
num = 1221
| a | b |
|---|---|
| 0 | 1221 |
| 1 | 122 |
| 12 | 12 |
| 122 | 1 |
| 1221 | 0 |
num = 2345
| a | b |
|---|---|
| 0 | 2345 |
| 5 | 234 |
| 54 | 23 |
| 543 | 2 |
| 5432 | 0 |
또! ! N (1 ≤ N ≤ 1,000,000) 이라고 소수배열의 범위를 1,000,000으로 하면 안된다 !
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
#include <iostream>
#include <math.h>
using namespace std;
int pn[10000000];
void prime(){
pn[0]=1;pn[1]=1;
for(int i=2;i<=sqrt(10000000);i++){
if(pn[i]==1) continue;
for(int j=2;i*j<=10000000;j++)
pn[i*j]=1;
}
}
bool pldr(int num){
string s=to_string(num);
int i=0,j=(int)s.length()-1;
while(i<j){
if(s[i]!=s[j])
return false;
i++;
j--;
}
return true;
}
int main(){
prime();
int n ; cin >> n;
for(int i=n;;i++){
if(pn[i]==1) continue;
if(pldr(i)==true){
cout << i << '\n';
break;
}
}
}