[Programmers] 소수만들기

 

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

브루트 포스 O(n³) 말고는 방법이 잘 생각나지 않는다.

투 포인터로 접근하는 문제는 아닌 듯하다.

bool is_Prime(int n);

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

bool is_Prime(int n)
{
    for(int i=2; i<=sqrt(n); i++)
        if(n%i == 0)
            return false;
    
    return true;
    
}