[C++] 백준 1747 - 소수&팰린드롬

문제 - 소수&팰린드롬 (Silver 1)

[백준 1747] https://www.acmicpc.net/problem/1747

풀이 전략

• 에라토스테네스의 체로 소수를 걸러낸 뒤 palindrome 수를 판별하는 함수를 만들어서 두 가지 조건의 교집합을 구한다.
• N의 최대 숫자가 크기 때문에 따로 const int로 선언해준다.
• 브루트포스 알고리즘으로 N부터 N의 최대 숫자까지 전체를 돌면서 소수를 걸러놓는다
• 투포인터를 사용해서 숫자를 string으로 바꾼 뒤 포인터를 이동시키면서 팰린드롬 수 인지 판별

참고

palindrome

: 101, 58385, 토마토, Tenet, 우영우 처럼 앞뒤를 뒤집었을 때 똑같은 수나 문자가 나오는 것을 팰린드롬이라고 한다.

에라토스테네스의 체

베르트랑 공준
소수의 연속합
위 두 문제에 설명해놔서 생략ㅎ

소스코드

#include <iostream>
#include <vector>
#include <string>
#include <cmath>
const int MAX_NUM=1100000;

using namespace std;

bool isPalin(int n){
    string numStr=to_string(n);
    int left=0;
    int right=numStr.length()-1;

    while(left<=right){
        if(numStr[left]!=numStr[right])
            return false;
        left++;
        right--;
    }
    return true;
}

int main(void){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int N;
    cin>>N;
    
    vector<int> A(MAX_NUM+1,1);
    A[0]=A[1]=0;

    for(int i=2;i<=sqrt(MAX_NUM);i++){
        if(A[i]==1){
            for(int j=i*i;j<=MAX_NUM;j+=i){
                A[j]=0;
            }
        }
    } // 기존과 다르게 MAX_NUM까지 전부 처리함
    int target=N;

    while(true){
        if(target>MAX_NUM){
            break;
        }
        if(A[target]==1 && isPalin(target)){
            cout<<target<<'\n';
            break;
        } // 소수이면서 팰린드롬이면 출력
        target++;
        // 아니면 다음으로 넘어감
    }

    return 0;
}

결과