프로그래머스 - 소수 만들기 (C#)

문제 설명

int형 배열의 숫자 중 3개의 수를 더했을 때 소수가 되는 경우의 개수를 구하는 문제입니다.

문제 풀이 전

먼저, 소수를 판별하는 방법은 약수가 2개인지 확인하는 기본적인 방법이 있습니다.

좀 더 빠른 방법은 제곱근을 이용하는 방법이 있습니다.

public bool IsPrime(int num) 
{
	int sqrt = (int) Math.Sqrt(num); 
    for (int i = 2; i <= sqrt; i++) 
    {
    	if (num % i == 0)
    	{
    		return false;
    	}
    }
    return true;
}

공식을 외울 필요 없이 필요할 때 복붙해서 쓰면 됩니다.

문제 풀이

소수가 되는 경우의 개수를 구하려면 결국 3개의 수를 더한 값을 모두 구해야 합니다.

3중 반복문을
i는 0부터 nums.Length - 2까지
j는 i + 1부터 nums.Length - 1까지
k는 j + 1부터 nums.Length까지

돌리면 중복으로 계산하는 것 없이 모든 경우의 수를 찾을 수 있습니다.

제출 코드

using System;

class Solution
{
    public int solution(int[] nums)
    {
        int answer = 0;
        
        for (int i = 0; i < nums.Length - 2; i++)
        {
            for (int j = i + 1; j < nums.Length - 1; j++)
            {
                for (int k = j + 1; k < nums.Length; k++)
                {
                    int num = nums[i] + nums[j] + nums[k];
                    if (IsPrime(num))
                    {
                        answer++;
                    }
                }
            }
        }

        return answer;
    }
    
    public bool IsPrime(int num) 
	{
		int sqrt = (int) Math.Sqrt(num); 
		for (int i = 2; i <= sqrt; i++) 
		{
			if (num % i == 0)
            {
                return false;                 
            }				
		} 
		return true; 
	}
}