[프로그래머스][LV 1][C++] 소수 만들기

숫자의 조합을 만들어서 소수인지 판별하면 되는 문제이다.

 

조합은 3중 for문을 사용해서 구현하였으며 소수 판별은 시간복잡도를 줄이기 위해 sqrt(num) 값까지만 계산하게 해두었다.

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

bool isPrime(int num){
    if(num<=2) return false;
    for(int i=2;i<=sqrt(num);i++){          //시간복잡도 줄이기
        if(num%i==0) return false;
    }
    return true;
}

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

    for(int i=0;i<nums.size();i++){
        for(int j=i+1;j<nums.size();j++){
            for(int h=j+1;h<nums.size();h++){
                int n= nums[i]+nums[j]+nums[h];     //조합고려
                if(isPrime(n)){
                    answer++;
                }
            }
        }
    }
    return answer;
}