프로그래머스 - 소수 만들기

문제

https://school.programmers.co.kr/learn/courses/30/lessons/12977

프로그래머스

3개 숫자의 합이 소수인지 판별하는 문제였다.

 

문제 풀이

에라토스테네스의 체를 이용했고 nums가 최대 50개로 작은 수여서 완전탐색으로 풀었다.

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

int isPrime[3001];

void calPrime(){
    fill(isPrime, isPrime+3000,1);
    isPrime[0] = 0;
    isPrime[1] = 0;
    
    for(int i=2;i*i<=3000;i++){
        if(isPrime[i] == 1){ //i가 소수
            for(int j=i*i;j<=3000;j+=i){
                if(j%i==0){
                    isPrime[j] = 0;
                }                
            }
        }
    }
}

int solution(vector<int> nums) {
    int answer = 0;

    int numSize = nums.size();
    calPrime();
    
    for(int i=0;i<numSize;i++){
        for(int j=i+1;j<numSize;j++){
            for(int k=j+1;k<numSize;k++){
                if(isPrime[nums[i]+nums[j]+nums[k]] == 1){
                    answer++;
                }
            }
        }
    }

    return answer;
}