백준 4241 - 소수 없는 수열

문제링크: https://www.acmicpc.net/problem/4241

구현 + 간단한 소수판정 문제이다.

배열v 뒤쪽에 원소를 추가할 때

1,2,3....d 까지의 합을
그리고
v.back()과 새로 추가하고 싶은(i)숫자의 합을

판단해야 한다는 점에 주의해서
구현해주면된다

#include<iostream>
#include<algorithm>
#include<vector>
#include<cstring>
using namespace std;
#define ll long long
const int MAX = 1000*1001/2 + 1;
int n,m,d;
bool is_prime[MAX];
bool used[MAX];
vector<int> v;
void init(){
    memset(is_prime,true,sizeof(is_prime));
    is_prime[0]=is_prime[1]=false;
    is_prime[2]=true;
    for(int i=4;i<MAX;i+=2) is_prime[i]=false;
    for(int i=3;i<MAX;i++){
        if(is_prime[i]){
            for(ll t = (ll)i*i;t<MAX;t+=i) is_prime[t] = false;
        }
    }
}
bool dfs(int cnt){
    if(cnt==m-n+1){
        for(int i=0;i<cnt-1;i++){
            cout<<v[i]<<",";
        }
        cout<<v[cnt-1]<<"\n";
        return true;
    }
    int ret = false;
    for(int i=n;i<=m;i++){
        if(used[i]) continue;
        int sum = 0;bool flag = true;
        
        if(v.size()>=1){
            int back = v[v.size()-1];
            int sum = back+i;
            if(is_prime[sum]) flag = false;
            // 1 3 5 4 .... 2
            //
            int cnt = d-2;
            for(int t = v.size()-2;t>=0&&cnt>0;t--,cnt--){
                sum+=v[t];
                if(is_prime[sum]){
                    flag = false;break;
                }
            }
            if(is_prime[sum]) flag = false;
        }
        if(!flag) continue;
        v.push_back(i);used[i]=true;
        ret|=dfs(cnt+1);
        if(ret) return ret;
        v.pop_back();used[i]=false;
    }
    return ret;
}
int main(){
    init();
    while(1){
        cin>>n>>m>>d;v.clear();
        if(n==0&&m==0&&d==0) break;
        memset(used,false,sizeof(used));
       
        bool flag = dfs(0);
        if(!flag) cout<<"No anti-prime sequence exists."<<"\n";

    }
}