신기한 소수

#include<iostream>
 
using namespace std;
 
int n;
int prime[] = { 2,3,5,7 };
bool primee(int x) {
    for (int i = 2; i * i <= x; i++) {
        if (x % i == 0) {
            //cout << "HELLO" << endl;
            return false;
        }
    }
    return true;
}
void go(int m, int cnt) {
    if (m == n) {
        cout << cnt << '\n';
        return;
    }
    else {
        if (m == 0) {
            for (int i = 0; i < 4; i++)
                go(1, prime[i]);
        }
        else {
            cnt *= 10;
            for (int i = 1; i <= 9; i++) {
                int c = cnt;
                c += i;
                if (primee(c))
                    go(m + 1, c);
            }
 
        }
    }
}
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
 
    cin >> n;
    
    go(0,0);
    return 0;
}

오랜만에 푸는 소수문제다

보통 에라토스 테네스의 체를 써서 푸는방법을 많이 써먹는데

이문제에서 에라토스 테네스의 체를쓰면 메모리 초과에 걸린다 (4MB 제한이다)

그리고 문제를 보면서 중요한 포인트는 1부터~9까지 모든숫자를 하나하나 다건드릴게아니라 

시작지점이 2,3,5,7을 최고자리수로 시작해서 하나씩 늘려가면서 소수검사만해보면되고 이또한 생각보다 많지않기떄문에 충분히 4MB와 시간제한을 만족하는 풀이를할수있다.