[프로그래머스] 소수 만들기

문제 설명

nums(길이:[3,50]) 배열 안에 있는 숫자(범위 : [1,1000])들을 3개씩 더해서 숫자를 만들 수 있다. 이렇게 만들어진 숫자들 중에 소수인 것들의 개수를 구하여라.

아이디어

예전에 프로그래머스 레벨 2에서 한자리 수가 적힌 숫자카드들이 있는데 그 카드를 조합(자리수는 마음대로)했을 때 소수를 만들 수 있는 경우의 수를 구하라는 문제가 있었다.
https://velog.io/@coding3392/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%EC%86%8C%EC%88%98%EC%B0%BE%EA%B8%B0
여기선 dfs를 통해 소수의 certification을 만들었는데
이번엔 소수 만드는 게 그냥 합이길래 50 C 3의 소수 certification을 다 만들어줬다.
에라스토테네스의 체를 이용해서 3000에 대한 소수 여부를 미리 만들어놔도 됐겠지만 그냥 하나의 숫자를 받았을 때 소수인지 판명해주는 is_sosu()를 통해 certification을 검사했다.

코드

#include <vector>
#include <iostream>
#include<algorithm>
#include<math.h>
using namespace std;

bool is_sosu(int n){//3부터 들어옴
    for(int i = 2;i<=sqrt(n);i++){
        if(n%i== 0){
            return false;
        }
    }
    return true;
}

int solution(vector<int> nums) {
    int answer = 0;//없으면 -1인가?
    vector<int> jevi;
    for(int i = 0;i<nums.size()-3;i++){
        jevi.push_back(0);
    }
    for(int i = 0;i<3;i++){
        jevi.push_back(1);
    }
    do{//조합
        int sum = 0;
        for(int i = 0;i<jevi.size();i++){
            if(jevi[i] == 1){
                sum+=nums[i];
            }
        }
        if(is_sosu(sum)){
            answer++;
        }
    }while(next_permutation(jevi.begin(),jevi.end()));
    return answer;
}