[시뮬레이션] 백준 2023번 - 신기한 소수

https://www.acmicpc.net/problem/2023

2023번: 신기한 소수

백준 2023번 신기한 소수 문제다.

이 문제는 소수의 성질을 활용해 앞에서부터 숫자를 만들어나간다.

먼저 큐에 2, 3, 5, 7을 넣어 시작할 수 있는 숫자들을 넣어둔 뒤,

하나씩 꺼내서 뒤에 붙여줄 수 있는 수를 붙인뒤 소수 검사를 하고 소수라면 큐에 넣는다.

이 과정을 반복해 소수인 것들만 큐에 담다가 N-1번 반복해 총 N자리의 신기한 소수를 큐에 완성하게 된다.

 

모든 과정이 끝나면 큐에는 순서대로 push해놨기 때문에 바로 출력하면 된다.

#include <iostream>
#include <queue>
using namespace std;
int N;
queue<int> q; 
bool prime(int num){
    for(int i=2;i*i<=num;i++){
        if(num%i==0)
            return false;
    }
    return true;
}
int main(){
    cin>>N;
    q.push(2); q.push(3);
    q.push(5); q.push(7);
    int num=0;
    int size=q.size();
    
    for(int i=1;i<N;i++){
        for(int j=0;j<size;j++){
            num=q.front();
            q.pop();
            for(int k=1;k<10;k++){
                if(prime(num*10+k))
                    q.push(num*10+k);
            }
        }
        size=q.size();
    }
    while(!q.empty()){
        cout<<q.front()<<endl;
        q.pop();
    }
    return 0;
}