문제 : www.acmicpc.net/problem/1747
에라토스테네스체
[ 알고리즘풀이 ]
N에서 시작해 소수이면서 팰린드롬인 숫자를 찾을 때까지 N보다 크거나 같은 수를 순회한다.
1) 소수인지 체크
: 에라토스테네스 체를 이용해 입력 최댓값인 100만 보다 넉넉히 큰 1000만까지 소수를 다 구해놓는다.
--> 입력 최대값인 100만을 입력했을 때 정답이 100,3001 이므로 1000만까지 안 해도 됐었다...!!
2) 팰린드롬인지 체크
: 숫자의 각 자리를 추출해서 vector에 담아두고 팰린드롬인지 체크하면 된다.
[ 코드구현 C++ ]
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
|
#include<iostream>
#include<vector>
using namespace std;
bool isPrime[10000001];
void eratos() {
isPrime[0] = isPrime[1] = true;
for (int i = 2; i <= 10000000; i++) {
if (!isPrime[i]) {
for (int j = 2 * i; j <= 10000000; j += i)
isPrime[j] = true;
}
}
}
bool isPalindrome(int x) {
vector<int> numbers;
while (x) {
numbers.push_back(x % 10);
x /= 10;
}
bool ans = true;
for (int i = 0; i < ((int)numbers.size() / 2); i++) {
if (numbers[i] != numbers[numbers.size() - 1 - i]) ans = false;
}
return ans;
}
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
eratos();
int N, x;
cin >> N;
x = N;
while (1) {
if (!isPrime[x] && isPalindrome(x)){
cout << x << '\n';
break;
}
x++;
}
return 0;
}
|
cs |
[ github ]
github.com/travelbeeee/ProblemSolving/blob/master/BOJ/BOJ1747.cpp
'Problem Solving > BOJ' 카테고리의 다른 글
[BOJ] 9202 : Boggle (0) | 2020.09.17 |
---|---|
[BOJ] 14226 : 이모티콘 (0) | 2020.09.15 |
[BOJ] 1107 : 리모컨 고치기 (0) | 2020.09.14 |
[BOJ] 17404 : RGB거리 2 (0) | 2020.09.03 |
[BOJ] 9576 : 책 나눠주기 (0) | 2020.09.02 |