코테 준비용 공부 - 소수 만들기

소수 만들기

일단 소수(prime number)에 관한 문제면
아마 어느정도 알고리즘 공부를 해 보신 분들은
에라토스테네스의 체가 떠오를 것이라고 생각한다.

그걸로 범위 내의 소수를 걸러낸 후에
결국 nums 안에 존재하는 3개짜리 조합을 다 찾으면 된다.
dfs를 하면 되겠지 싶기도 했지만,

nums의 길이 자체가 50이 한계고
50^3 을 해도 대략 10^5정도니까..
매우 적은 시간이 걸린다.

문제의 조건에 제한시간이 없으므로
그냥 간단한 방법으로 때려박아서 풀었다.

소스코드

#include <vector>
#include <iostream>
using namespace std;
int dfs(int, vector<int>& );
bool prime[3001]={0};
int answer=0;
vector<int> v;
int solution(vector<int> nums) {
    for(int i=2;i<=3000;i++){
        if(prime[i]) continue;
        int j=2;
        while(i*j<=3000){
            prime[i*j]=true;
            j++;
        }
    }
    for(int i=0;i<nums.size()-2;i++){
        for(int j=i+1;j<nums.size()-1;j++){
            for(int k=j+1;k<nums.size();k++){
                	if(!prime[nums[i]+nums[j]+nums[k]]){
                    answer++;
                }
            }
        }
    }
    return answer;
}