티스토리 뷰

알고리즘 관련/BOJ

BOJ)2023 신기한 소수

JASON 자손9319 2017. 10. 16. 16:38

문제: icpc.me/2023


N자리의 신기한 소수를 모두 출력하는 문제이다.


문제를 잘 생각해보면 N자리의 신기한 소수는 결국 N-1자리의 신기한 소수로부터 파생된다는 걸 알 수 있다.


게다가 예제를 보면 그 수가 얼마 안되기 때문에 N-1자리의 신기한 소수들에서 파생되는 수들에 대해서만 sqrt(Number)시간에 소수여부 검사를 해주면 빠르게 구해줄 수 있다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
vector<int> v[10];
bool isp(int x) {
    for (int i = 2; i <= sqrt(x); i++) {
        if (!(x%i))return false;
    }
    return true;
}
int main() {
    v[0].push_back(2);
    v[0].push_back(3);
    v[0].push_back(5);
    v[0].push_back(7);
    for (int i = 1; i < 8; i++) {
        for (auto next : v[i - 1]) {
            for (int j = 0; j < 10; j++) {
                int curr = next * 10 + j;
                if (isp(curr))v[i].push_back(curr);
            }
        }
    }
    int n;
    scanf("%d"&n);
    for (auto next : v[n - 1])
        printf("%d\n", next);
    return 0;
}
cs


'알고리즘 관련 > BOJ' 카테고리의 다른 글

BOJ)5846 Tractor  (0) 2017.10.24
BOJ)5849 Cow Crossings  (0) 2017.10.24
BOJ)2023 신기한 소수  (0) 2017.10.16
BOJ)13212 Random  (0) 2017.10.16
BOJ)13213 Binary Roads  (0) 2017.10.16
BOJ)11442 홀수번째 피보나치 수의 합  (0) 2017.10.14
TAG
댓글
댓글쓰기 폼