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

자연수가 담겨있는 배열 nums 가 주어졌을 서로다른 3개를 골라 그 합이 소수가 되는 경우의 수를 반환하는 문제였다.

풀이

1. nums에는 1000 이하의 자연수들이 들어있기 때문에 3000이하의 소수들을 미리 구해준다.

2. 3중 for 문을 돌면서  서로다른 3개의 원소를 골라 합이 소수인지 확인한다.

#include <vector>
#include <iostream>
using namespace std;

int num[3001];
int solution(vector<int> nums) {
    int answer = -1;

    num[0]=true;
    num[1]=true;

    for(int i=2;i*i<3001;i++){
        if(!num[i])
        for(int j = i*i;j<=3000;j+=i){
            num[j]=true;
        }

    }

    int cnt=0;
    int nums_size=nums.size();
    for(int i=0;i<nums_size;i++){
        for(int j=i+1;j<nums_size;j++){
            for(int k=j+1;k<nums_size;k++){
                if(!num[nums[i]+nums[j]+nums[k]])
                    cnt++;
            }
        }
    }
    answer=cnt;
    return answer;
}