백준2023 - 신기한 소수

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

2023번: 신기한 소수

우선 2, 3, 5, 7이 한자리 소수니까 해당 숫자에서 탐색을 시작한다. 2자리 수부터 마지막 자리로 짝수가 오면 소수가 아니니까 홀수만 판단한다. 소수를 판단 할 때는 해당 숫자의 루트값을 구하여 자연수를 끝 값으로 바꾼 뒤 3부터 끝 값까지 홀수만 탐색해 나가는 방식을 썼다. 소수로 판단하는 숫자는 무조건 홀수만 매개변수로 넘어가기 때문이다.

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

int n;
int mat[4] = {2, 3, 5, 7};

bool find_prime(int x) {
    int stop = sqrt((double)x);
    
    for(int i = 3; i <= stop; i += 2){
        if(x % i == 0) {
            return false;
        }
    }
    return true;
}

void func(int x, int cnt) {
    if(cnt == n) {
        cout << x << '\n';
        return;
    }
    for(int i = 1; i <= 9; i += 2) {
        if(find_prime(x * 10 + i)) {
            func(x * 10 + i, cnt + 1);
        }
    }
}

int main() {
    cin >> n;
    
    for(int i = 0; i < 4; i++) {
        func(mat[i], 1);
    }
}