[BOJ/백준][Gold4] 3671 : 산업 스파이의 편지 (C++)

https://www.acmicpc.net/problem/3671

3671번: 산업 스파이의 편지

 

[난이도] Gold4
[유형] 브루트포스

[풀이]
에라토스테네스의 체를 이용해 0~9999999 까지의 소수를 기록해놓고
만들 수 있는 모든 숫자를 브루트포스를 이용해 구한 뒤 소수이면 set에 저장한다.
이 set의 크기가 정답이다.

 

#include <iostream>
#include <string>
#include <set>
#include <vector>
#include <algorithm>
using namespace std;
bool prime[10000000];
int t;
int main(){
    ios_base::sync_with_stdio();
    cin.tie();
    cout.tie();
    cin >> t;
    prime[0]=prime[1]=1;
    for(int i=2;i<10000000;i++){
        for(int j=i*2;j<10000000;j+=i){
            prime[j]=1;
        }
    }
    while(t--){
        string s;
        cin >> s;
        int n = s.size();
        set<int> st;
        for(int i=1;i<(1<<n);i++){
            string a;
            for(int j=0;j<n;j++){
                if((i&(1<<j))>0) a.push_back(s[j]);
            }
            
            sort(a.begin(),a.end());
            
            do{
                int num = stoi(a);
                if(!prime[num]) st.insert(num);
            }while(next_permutation(a.begin(),a.end()));
        }
        cout << st.size();
    }
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold4/3671.cpp