C++:: 프로그래머스 < 소수 만들기 >

에라토스테네스의 체를 사용하여 소수를 구하고 하면 되는 문제이다. 크게 어렵지 않다.

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

int solution(vector<int> nums) {
    sort(nums.begin(), nums.end(), greater<int>());
    int n = nums[0]+nums[1]+nums[2], answer = 0;
    vector<bool> eratos(n+1, true);
    for (int i=2;i*i<=n;i++) {// 에라토스테네스의 체
        if (eratos[i]) {
            for (int j=i*i;j<=n;j+=i) {
                eratos[j] = false;
            }
        }
    }
    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 (eratos[nums[i]+nums[j]+nums[k]]) answer++;
            }
        }
    }
    return answer;
}