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

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

프로그래머스

 

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

bool isprim(int n)
{
    int cnt=0;
    for(int i=1;i*i<=n;i++)
    {
        if(n%i==0){
            cnt++;
            if(i!=n/i)
                cnt++;
        }
    }
    if(cnt<=2)return true;
    else return false;
}

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++)
            {
                if(isprim(nums[i]+nums[j]+nums[k]))
                    answer++;
            }
        }
    }
    
    return answer;
}

 

주어진 int 형 벡터에서 서로다른 3개를 뽑아더한 값이 소수인지를 판단하는 것이다. 

최대 몇개의 소수를 만들 수 있는가를 구하는 문제이다. 

 

경우의 수를 구하는 문제기 때문에 3중 반복문을 통해서 모든 경우에서 소수인지를 판단하였다.

소수인지 판단하는 것은 isprim 이라는 함수를 통해서 해결했는데

약수를 구할때의 알고리즘을 가져와서 사용하였다.