[프로그래머스] [C#] 소수 만들기

안녕하세요.

오늘은 프로그래머스 코딩테스트 연습 문제인 "소수 만들기" 를 풀어 보았습니다.

 

문제 링크

---

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

 

 

문제 풀이 방법

---

코드 실행시간을 줄이기 위해 소수를 구하는 IsPrime함수에서 num의 제곱근을 내림하여 나온 값까지만 for문을 돌게 하였습니다.

 

그 결과 평균 약 0.40ms 정도의 속도로 테스트를 통과하였습니다.

 

코드

---

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

        return answer;
    }

    private bool IsPrime(int num)
    {
        // 제곱근을 내림한 값까지 돌면 효율적으로 소수인지 확인할 수 있습니다.
        int sqrNum = (int)Math.Sqrt(num);

        // 0, 1은 확인하지 않습니다.
        for (int i = 2; i <= sqrNum; i++)
        {
            if (num % i == 0)
            {
                return false;
            }
        }

        return true;
    }
}

 

감사합니다.