[Level 1] 소수 만들기 (C++/Python)

C++)

#include <vector>
#include <iostream>
#include <array>
#define MAX_NUM 3000  // 입력된 값들의 최대 합은 998+999+1000

using namespace std;

array<bool, MAX_NUM> prime;

int solution(vector<int> nums) {
    int answer = 0;
    
    // 소수 먼저 구하기
    for(int i = 2; i * i <= MAX_NUM; i++) {
        if(!prime[i]) {
            for(int j = i * i; j <= MAX_NUM; j+=i) {
                prime[j] = true;
            }
        }
    }
    
    // 3개의 수의 합 구하기
    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.at(i) + nums.at(j) + nums.at(k)])
                    answer++;
            }
        }
    }
    
    return answer;
}

 

 

 

Python)

def solution(nums):
    arr = [False] * 3000
    
    for i in range(2, int(3000**0.5)):
        for j in range(i*i, 3000, i):
            if arr[j]:
                continue
            arr[j] = True
            
    ans = 0
    for i in range(len(nums)):
        for j in range(i+1, len(nums)):
            for k in range(j+1, len(nums)):
                if not arr[nums[i]+nums[j]+nums[k]]:
                    ans += 1
    return ans