C++ / 프로그래머스 / 소수 만들기

문제

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

코딩테스트 연습 - 소수 만들기

문제풀이

처음에 비트 마스크 문제인 줄 알았는데 다시 보니 서로 다른 숫자 3개를 고르는 문제였다.

따라서 for문을 중첩해서

num1: nums[0]~

num2: nums[1]~

num3: nums[2]~

이런 식으로 구하면 되겠다는 생각을 했다.

그리고 반복하면서 숫자 3가지를 더해주고

for문으로 1부터 sum의 제곱근까지 반복하면서 1 이외의 약수가 나오는지 체크해주고, 약수가 더 나온다면 소수가 아니므로 넘어가고 더 안 나온다면 소수이므로 answer++을 해준다.

 

 

코드

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

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

    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) {
                int sum = nums[i] + nums[j] + nums[k];
                int cnt = 0;
                for (int l = 1; l <= sqrt(sum); ++l) {
                    if (sum % l == 0) {
                        cnt++;
                    }
                }
                if (cnt == 1) answer++;
            }
        }
    }

    return answer;
}