3671 산업 스파이의 편지

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

7자리 자연수까지의 모든 소수를 에라토스테네스의 체(Sieve of Eratosthenes)를 이용하여 미리 구하고 브루트 포스(Brute Force)로 만들 수 있는 모든 숫자를 만들어서 소수인지 확인한다. 에라토스테네스의 체는 O(NloglogN)에 1~N까지 모든 소수를 구하는 알고리즘이다. 최대 7자리이므로 10000000*log(log(10000000)) := 8450980

+ 모든 경우에 대하여

이므로 대략 1억번의 연산이 넘지 않음을 알 수 있기에 시간 내에 해결할 수 있음을 알 수 있다.

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
 
bool p[10000000],c[10000000];
int t;
string s;
 
int solve(string &s)
{
    int ans=0,size=s.size();
    sort(s.begin(),s.end());
    do
    {
        for(int i=0;i<size;i++)
        {
            for(int j=i+1;j<=size;j++)
            {
                int n=stoi(s.substr(i,j));
                if(!c[n] && !p[n]) c[n]=true,ans++;
            }
        }
    } while(next_permutation(s.begin(),s.end()));
    fill_n(c,10000000,0);
    return ans;
}
 
int main()
{
    p[0]=p[1]=true;
    for(int i=2;i*i<10000000;i++) if(!p[i]) for(int j=2*i;j<10000000;j+=i) p[j]=true;
    cin>>t;
    while(t--) cin>>s,cout<<solve(s)<<'\n';
    return 0;
}