[백준 2023] 신기한 소수 [C]

백준 - 2023

---

풀이

8자리수의 소수를 확인하기 위해 1e8만큼의 공간을 할당하면 메모리 제한에 막힌다.

심지어 조건에 맞는 모든 소수의 개수가 100개도 안된다.

 

때문에, 다음과 같은 규칙을 찾아 문제를 해결했다.

• N의 자릿수는 2, 3, 5, 7 이어야 한다.
• 2를 제외한 모든 짝수는 소수가 아니기 때문에 홀수만 탐색해야 한다.

---

소스코드

#include <stdio.h>
#include <math.h>
int prime(int num){
    int sq = sqrt(num);
    for (int i = 2; i <= sq; i++)
        if (num%i == 0) return 0;
    return 1;
}
void dfs(int num, int digit){
    if (digit == 1) printf("%d\n", num);
    else
        for (int i = 1; i < 10; i += 2)
            if (prime(num*10 + i))
                dfs(num*10 + i, digit - 1);
}
int main(){
    int N;
    scanf("%d", &N);
    dfs(2, N);
    dfs(3, N);
    dfs(5, N);
    dfs(7, N);
}

---

출처

2023번: 신기한 소수