[C/C++] 백준 #2023 신기한 소수(수학)

N자리 소수중에서 하위자리를 빼나가도 소수가 되는 수들은 상당히 많습니다.  첫자리를 제외하고 나머지는 모두 홀수로 이루어져 있어야 하죠.  물론 5와 같이 10의 소인수인 수는 제외입니다.

 

Prime numbers

 

이 문제를 풀기 위한 접근은 간단합니다.

 

1) 초기 시작수 2, 3, 5, 7을 리스트에 넣습니다.

2) 이곳에 1, 3, 7, 9를 붙여서 소수가 된다면 그 수를 리스트에 넣습니다.

3) N자리수가 될때까지 2)를 반복합니다.

 

이렇게 하면 손쉽게 결과를 출력할 수 있습니다.

for 루프 쓸 때, 1, 3, 7, 9만 붙이면 되는데, 그냥 5도 같이 붙였습니다.  크게 성능 이슈가 있지는 않기 때문에, 문제 통과하는데에는 이상이 없었습니다.

 

제가 작성한 소스입니다

//--------------------------------------
//    baekjoon #2023 - Magic Prime Number
//        - by Edan
//        - created at 2019-06-16
//--------------------------------------
#include <stdio.h>

bool isprime(int n){for(int p = 3;p*p<=n;p+=2)if(n%p==0)return false;return true;}
void listprime(int s, int c, int n)
{
    if(c == n) { printf("%d\n", s); return; }
    for(int i = 1; i < 10; i += 2)
    {
        int t = s * 10 + i;
        if(!isprime(t)) continue;
        listprime(t, c + 1, n);
    }
}
int main()
{
    int n, v[4] = {2, 3, 5, 7};
    scanf("%d", &n);
    for(int i = 0; i < 4; i++) listprime(v[i], 1, n);
}