https://www.acmicpc.net/problem/1747
1747번: 소수&팰린드롬
어떤 수와 그 수의 숫자 순서를 뒤집은 수가 일치하는 수를 팰린드롬이라 부른다. 예를 들어 79,197과 324,423 등이 팰린드롬 수이다. 어떤 수 N (1 ≤ N ≤ 1,000,000)이 주어졌을 때, N보다 크거나 같고,
www.acmicpc.net
그냥 에라토스테네스로 소수 구하고
팰린드롬수 체크하면 끝
|
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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
|
#include <iostream>
#include <cmath>
#include <string>
using namespace std;
bool isPalin(int prime)
{
// 숫자를 문자열로 변환
string tmp = to_string(prime);
// 문자열을 배열로 변환
char const* tmp_arr = tmp.c_str();
int s = 0;
int e = tmp.size() - 1;
while (s < e)
{
if (tmp_arr[s] != tmp_arr[e])
return false;
s++;
e--;
}
return true;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
long n;
cin >> n;
long arr[10000001];
for (int i = 2; i < 10000001; i++)
arr[i] = i;
// 제곱근까지만 수행
for (int i = 2; i <= sqrt(10000001); i++)
{
if (arr[i] == 0)
continue;
// 배수 지우기
for (int j = i + i; j < 10000001; j += i)
{
arr[j] = 0;
}
}
int i = n;
while (true)
{
if (arr[i] != 0)
{
int result = arr[i];
if (isPalin(result))
{
cout << result << '\n';
break;
}
}
i++;
}
return 0;
}
|
cs |
// 숫자를 문자열로 변환
string tmp = to_string(prime);
// 문자열을 배열로 변환
char const* tmp_arr = tmp.c_str();
c_str() 함수!
내용이 변경되면 안 되는 제약 조건을 가진, char형 포인터를 리턴합니다.
'정수론' 카테고리의 다른 글
| 오일러 피 (0) | 2023.08.19 |
|---|---|
| 제곱 ㄴㄴ 수 (어렵) (0) | 2023.08.02 |
| 거의 소수 (0) | 2023.08.02 |
| 에라토스테네스의 체 (0) | 2023.08.02 |
