[백준 2023] 신기한 소수

• 안녕하세요!! BlockDMask 입니다!!

• 오늘의 문제 신기한 소수. 풀어보겠습니다.
  170906 문제 빼먹음 -> 171105 완료

0. 제목

• 백준 2023 신기한 소수

• BOJ 2023 신기한 소수

• prime number

1. 문제 설명

• 소수 7331을 보면
  7331도 소수이고
  신기하게도 
  733도 소수
  73도 소수
  7 도 소수 입니다.

• 즉, 왼쪽부터 1자리, 2자리, 3자리, 4자리 수 모두 소수이다!
  이러한 소수를 신기한 소수라 이름 붙였다.
  N자리의 숫자 중에서 어떤 수 들이 신기한 소수인지 궁금해졌다.
  N이 주어졌을 때, N자리 신기한 소수를 모두 찾아보자.

• 입력 
  첫째 줄에 N (1<= N <= 8) 이 주어집니다.

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

2. 풀이 과정

• 1) 각 자리수의 맨 앞 첫 자리는 한자리 수 소수가 와야하므로 2, 3, 5, 7 만 올 수 있습니다.

• 2) 첫 자리를 2, 3, 5, 7로 고정한 뒤 첫자리(10*A)와 그다음 자리수(B)를 합친게 소수 인지
  **이때 B는 짝수 이면 2로 나누어져서 소수가 아니므로 홀수를 넣습니다.

• 3) 그 수가 소수이면 소수인 수 A에 10*A + B 를 한 것이 또 다시 소수인지 쭉쭉 판별하여 자리수가 다할때 까지 진행하면 됩니다.
  
  

• recursive 방식의 dfs 문제로 판단하고 풀었습니다.

3. 소스 코드

//https://www.acmicpc.net/problem/2023
//BOJ_2023_interestingPrimeNumber
 
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
 
void input(int & n) {cin >> n;}
 
bool isPrime(int num){
    if(num<2) return false;
    for(int i=2; i*i<=num; i++){
        if(num%i == 0) return false;
    }
    return true;
}
 
void recursive(int first, int n){
    //자릿수(n)가 0이 되면 그 수 출력
    if(n==0) printf("%d\n", first);
    
    for(int i=1; i<10; i+=2){   //홀수만 더해주기
        int tmp = first*10 + i;
        if(isPrime(tmp)){
            recursive(tmp, n-1);
        }
    }
 
}
int main(void){
    int n;
    input(n);
 
    //맨 앞 자릿수가 prime number 이어야합니다
    int prime[4] = {2, 3, 5, 7};
    for(int i=0; i<4; i++){
        recursive(prime[i], n-1);
    }
    return 0;
}

4. 인증

문제 출처 - https://www.acmicpc.net/problem/2023

감사합니다.