[Algorithm] 소수 만들기

문제 설명

주어진 숫자 중 3개의 수를 더했을 때 소수가 되는 경우의 개수를 구하려고 합니다. 

숫자들이 들어있는 배열 nums가 매개변수로 주어질 때, nums에 있는 숫자들 중 서로 다른 3개를 골라 더했을 때 소수가 되는 경우의 개수를 return 하도록 solution 함수를 완성해주세요.

 

문제 풀이

1. 소수 판별 함수를 작성한다.
   • 2부터 숫자의 제곱근까지 나누어 떨어지는 경우가 있으면 소수가 아니다.
2. 3개 숫자 조합을 생성한다.
   • 3개의 중첩된 반복문으로 모든 조합을 확인한다.

 

코드 작성

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

bool isPrimeNum(int num)
{
    int sqrtNum = static_cast<int>(sqrt(num));
    for (int i = 2; i <= sqrtNum; i++)
    {
        if (num % i == 0)
            return false;
    }
    
    return true;
}

int solution(vector<int> nums) {
    int answer = 0;
    int size = nums.size();
    for (int i = 0; i < size; i++)
    {
        for (int j = i + 1; j < size; j++)
        {
            for (int z = j + 1; z < size; z++)
            {
                int sum = nums[i] + nums[j] + nums[z];
                 if (isPrimeNum(sum))
                    answer++;
            }
        }
       
    }
    
    return answer;
}