(프로그래머스 c++)소수 만들기

주어진 배열에서 3개의 수를 더했을 때 소수인지 판별하면 된다..!

 

우선 1000 이하의 자연수이고, 3개의 수를 더해야 하기 때문에 구할 수 있는 소수의 최댓값은 1000 + 999 + 998이다.

2997이므로 소수를 판별하는 배열 prime[2998]을 선언하여 false로 초기화해준다.

 

(소수 판별하는 for문의 설명)

https://eunchanee.tistory.com/18

(프로그래머스 c++)소수 찾기

그리고 nums를 오름차순으로 정렬해주도록 한다..!

 

이제 3중 for문을 이용하여 3개의 수를 더한 값이 소수인지(false 이면 소수) 확인한 후

answer++을 하면 된다..!

#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;

int solution(vector<int> nums) {
    int answer = 0;
    bool prime[2998] = {false, };
    
    for(int i = 2; i < 2998; i++)
        for(int j = i + i; j < 2998; j += i)
            prime[j] = true;
    
    sort(nums.begin(), nums.end());
    
    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(prime[nums[i] + nums[j] + nums[k]] == false)
                    answer++;

    return answer;
}