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

www.acmicpc.net/problem/1747

1747번: 소수&팰린드롬

 

소수이면서 펠린드롬인 수를 찾는 문제이다.

 

에라토스테네스의 체 알고리즘을 사용하면 쉬운 문제다.

에라토스테네스의 체란 소수를 판별하는 일종의 브루트포스 알고리즘이다.

꼭 체에 수를 걸러서 소수만 남기는 것 같다는 이유와 그리스의 수학자 에라토스테네스의 이름을 따서 에라토스테네스의 체라고 불린다.

더 자세한 설명은 여기로! 에라토스테네스의 체

 

팰린드롬이란 한글로 회문 즉 앞에서부터 읽어도 뒤에서 부터 읽은 것과 같은 글을 의미한다.

회문의 예시

 

설명은 주석으로 대체

#include <iostream>
using namespace std;

int main()
{
    int N, a[1004000];
    scanf("%d",&N);
    
    //에라토스테네스의 체로 거르기
    for(int i=0;i<1004000;i++)
    {
        a[i]=i;
    }
    for(int i=2;i<1004000;i++)
    {
        if(a[i]==0) continue;
        for(int j=i+i;j<1004000;j+=i)
        {
            a[j]=0;
        }
    }
    
    //모든 빈공간에 숫자 집어넣기
    int tmp=1003001, d;
    for(int i=1003999;i>0;i--)
    {
        if(a[i]!=0)
        {
            int len=0;
            int b[10], c[10];
            bool isprd=true;
            for(int j=0;j<10;j++) // b,c 초기화
            {
                b[j]=-1;
                c[j]=-1;
            }
            d=a[i];
            while(d>0) // 몇자리의 수인지 길이 구하기
            {
                d/=10;
                len++;
            }
            d=a[i];
            for(int j=0;j<len;j++) // 배열 b에 한 숫자씩 차례대로 넣기
            {
                b[j]=d%10;
                d/=10;
            }
            int l=len-1;
            for(int j=0;j<len;j++) // 배열 c에 한 숫자씩 차례대로 거꾸로 넣기
            {
                c[j]=b[l--];
            }
            
            for(int j=0;j<(len/2);j++) // 배열 b와 c를 비교해서 펠린드롬인지 검증하기
            {
                if(b[j]!=c[j])
                {
                    isprd=false;
                }
            }
            
            if(isprd) // 소수이고 펠린드롬이라면 이 이후의 수들을 이 수로 체움
            {
                tmp=a[i];
            }
            else // 소수이지만 펠린드롬이 아니라면 가장 가까운 크거나 같은 소수이며 펠린드롬인 수로 체움
            {
                a[i]=tmp;
            }
        }
        else // 소수가 아니면 가장 가까운 크거나 같은 소수이며 펠린드롬인 수로 체움
        {
            a[i]=tmp;
        }
    }
    
    a[1]=2; // 1은 소수가 아님
    printf("%d",a[N]);
    
    return 0;
}