[BOJ] 3671 - 산업 스파이의 편지

[백준] 3671 - 산업 스파이의 편지

충분히 큰 수까지의(여기서는 7자릿수까지 가능하므로 10,000,000까지 구해본다) 소수를 미리 구해놓는다. 이후 매 수를 입력받을 때 마다 모든 경우의 수를 돌려보며 소수일 경우 카운트해준다.

소스코드

#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <iostream>
#include <cmath>
#include <queue>
#include <functional>
#include <string.h>
#include <ctype.h>
#include <stack>
#include <set>
#include <stack>
using namespace std;
typedef long long ll;

int cnt;
bool decimal[10000000] = { true, true }, ck[10];
char str[10], tmp[10];
map<int, bool> ck2;

void func() {
    char buf[10] = { NULL, };
    strcpy(buf, tmp);
    sort(buf, buf + strlen(buf));
    do {
        int now = atoi(buf);
        if (!ck2[now] && !decimal[now]) {
            ck2[now] = true; cnt++;
        }
    } while (next_permutation(buf, buf + strlen(buf)));
}

void go(int idx, int now) {
    if (idx >= strlen(str)) return;
    for (int i = now + 1; i < strlen(str); i++) {
        if (!ck[i]) {
            ck[i] = true;
            tmp[idx] = str[i];
            func();
            go(idx + 1, i);
            ck[i] = false;
            tmp[idx] = NULL;
        }
    }
}

int main(void) {
    int t;

    for (int i = 2; i < 10000000; i++) {
        if (decimal[i]) continue;
        for (int j = 2; i * j < 10000000; j++)
            decimal[i * j] = true;
    }

    scanf("%d", &t);
    
    for (int T = 0; T < t; T++) {
        map<int, bool>().swap(ck2);
        scanf("%s", str);
        cnt = 0;
        go(0, -1);
        printf("%d\n", cnt);
    }
    return 0;
}