백준 및 코드포스

태그는 백트래킹이다.
하지만 내 맥북의 vscode에서 pair 기능이 작동하지 않아서 pair를 사용하지 않고 풀었다.
메모리 제한이 작으며, 8자리 수까지 판별하는 문제라 에라토스테네스의 체를 사용할 수는 없다.

내가 푼 방법이다.

0. 한 자리 소수는 2, 3, 5, 7 뿐이다.
=> 큐에 2, 3, 5, 7을 넣어준다.

1. 큐에 담긴 n자리 소수의 뒷자리에 1,3,7,9를 넣어서 n + 1자리의 숫자를 만든다.

1 ~ 3의 과정을 n - 1번 반복하면 n자리 수의 소수만 큐에 남는다.

#include <iostream>
#include <queue>
#include <cmath>
using namespace std;

int dx[4] = {1,3,7, 9};
int n, ans;
queue <int> Q;

void Prime() {
    int size = Q.size();
    while(size--){
        for(int i = 0; i < 4; i++) {
            bool isPrime = 1;
            int cur = Q.front() * 10 + dx[i];

            for(int j = 3; j <= sqrt(cur); j++) {
                if(cur % j == 0){ 
                isPrime = 0;
                break;
                }
            }
            if(isPrime) {
                Q.push(cur);
            }
        }
        Q.pop();
    }
}

int main() {
    Q.push(2);
    Q.push(3);
    Q.push(5);
    Q.push(7);
    cin>>n;

    for(int i = 1; i < n; i++) {
        Prime();
    }
    
    ans = Q.size();
    for(int i = 0; i < ans; i++) {
        cout<<Q.front()<<'\n';
        Q.pop();
    }
}