백준 2023 신기한 소수 C++

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

자리수가 추가될 때마다 현재 상태의 수가 소수인지 아닌지를 판별해주면 된다.

가령 7331을 만들기 위해서, 처음에 7을 골라서 확인하고, 73을 확인하고, 733을 확인하고 ... 이런 흐름이다.

처음에 2를 고르고, 다음에 21이 나왔을텐데, 21은 소수가 아니기 때문에 21#$!@#는 더이상 확인할 필요가 없는 것이다.

신경써줄 부분은, 소수 판별 함수에서 1은 바로 소수가 아님을 반환하는 것과, 가장 큰 자리의 수가 0이 되지 않도록 해주는 부분이다.

/*특정 수열이 만들어질 때마다
소수 여부 판별해서, 소수 아닐 때만 이어서 진행*/
#include<iostream>
#include<vector>
using namespace std;
int n, arr[10], st = 0;
bool isPrime(int val) {
    if (val == 1) return false; //1은 소수가 아님
    for (int i = 2; i*i <= val; i++)
        if (val % i == 0) return false;
    return true;
}
void backTracking(int k, int num) {
    
    //소수검사
    if (k != 0) 
        if (!isPrime(num)) return;
    
    if (k == n) {
        cout << num << '\n';
        return;
    }
 
    //가장 큰 자리수로 0못오게
    if (k == 0)st = 1;
    else
        st = 0;
 
    for (int i = st; i <= 9; i++) 
        backTracking(k + 1, num * 10 + i);
}
int main(void) {
    cin >> n;
    backTracking(0,0);
    
    return 0;
}