Home BOJ - 1747 - 소수&팰린드롬
Post
Cancel

BOJ - 1747 - 소수&팰린드롬

BOJ - 1747 - 소수&팰린드롬

문제


1747번: 소수&팰린드롬

https://user-images.githubusercontent.com/71277820/167538836-c8e8c34a-6108-4c9b-8582-7d4e00e134fd.png

문제 개념


문제

어떤 수와 그 수의 숫자 순서를 뒤집은 수가 일치하는 수를 팰린드롬이라 부른다. 예를 들어 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시에도 같은 경우를 구함.

Reference & 다른 PS 모음집


GitHub - ggh-png/PS: 2021.01.11 start

[알고리즘] 에라토스테네스의 체 (C++) - 소수 찾기

This post is licensed under CC BY 4.0 by the author.