2023. 신기한 소수 GOLD V(C++)

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

2023번: 신기한 소수

문제

수빈이가 세상에서 가장 좋아하는 것은 소수이고, 취미는 소수를 가지고 노는 것이다. 요즘 수빈이가 가장 관심있어 하는 소수는 7331이다.

7331은 소수인데, 신기하게도 733도 소수이고, 73도 소수이고, 7도 소수이다. 즉, 왼쪽부터 1자리, 2자리, 3자리, 4자리 수 모두 소수이다! 수빈이는 이런 숫자를 신기한 소수라고 이름 붙였다.

수빈이는 N자리의 숫자 중에서 어떤 수들이 신기한 소수인지 궁금해졌다. N이 주어졌을 때, 수빈이를 위해 N자리 신기한 소수를 모두 찾아보자.

입력

첫째 줄에 N(1 ≤ N ≤ 8)이 주어진다.

출력

N자리 수 중에서 신기한 소수를 오름차순으로 정렬해서 한 줄에 하나씩 출력한다.

 

#include <iostream>
#include <queue>
 
using namespace std;
 
 
bool check(int x)
{
    if(x<2) return false;
 
    for(int i=2;i*i<x;i++)
        if(x%i == 0 ) return false;
    return true;
 
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin>>n;
    queue<int> Q;
    Q.push(2);
    Q.push(3);
    Q.push(5);
    Q.push(7);
    while(--n)
    {
        int qsize = Q.size();
        while(qsize--)
        {
            int x = Q.front();
            Q.pop();
            for(int i=1;i<10;i+=2)
            {
                if(i == 5) continue;
                if(check(x*10 + i))
                    Q.push(x * 10 + i);
            }
        }
    }
 
    while(!Q.empty())
    {
        cout<<Q.front()<<'\n';
        Q.pop();
    }
 
    return 0;
}
 

처음 에라토스테네스의 체를 이용하려고 했는데 8자리 숫자 까지 해야해서 메모리가 부족할거 같았다.

그래서 그냥 그때마다 소수인지 판별하는게 빠르겠다고 생각하고 문제를 풀었다.

2,3,5,7 대로 큐를 이용하고 오름차순으로 검사를 하면 자동적으로 오름차순 정렬이 되서 큐를 이용했다.

 

1. 2,3,5,7은 먼저 한 자리 소수이므로 큐에 먼저 집어 넣는다.

2. n은 몇 자리 숫자 인지를 나타내고 qsize를 이용한 이유는 현재 큐의 갯수만큼 한 바퀴 더 돌아야 하기 때문

3. for문으로 검사를 하는데 i가 짝수거나 끝이 5로 끝나면 무조건 소수가 아니므로 홀수이면서 끝자리가 5가 아닌것만 검사.

4. pop 하면서 출력