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

최애뎡 2021. 9. 8. 00:10

728x90

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

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

주어진 숫자 중 3개의 수를 더했을 때 소수가 되는 경우의 개수를 구하려고 합니다. 숫자들이 들어있는 배열 nums가 매개변수로 주어질 때, nums에 있는 숫자들 중 서로 다른 3개를 골라 더했을 때

programmers.co.kr

using System;
using System.Collections.Generic;

class Solution
{
    public int solution(int[] nums)
    {
        int answer = 0;
        
        Array.Sort(nums);
        int max = nums[nums.Length - 1] + nums[nums.Length - 2] + nums[nums.Length - 3];

        List<bool> list_num = new List<bool>(){ false, false };
        for (int i = 1; ++i <= max;) list_num.Add(true);
        for (int i = 1; ++i <= max;)
            if(list_num[i] == true)
            {
                for (int j = i * 2; j <= max; j += i) 
                    list_num[j] = false;                    
            }

        for(int i = -1; ++i < nums.Length - 2;)
            for(int j = i + 1; j < nums.Length - 1; j++)
                for(int x = j + 1; x < nums.Length; x++)
                {
                    int sum = nums[i] + nums[j] + nums[x];
                    if(list_num[sum]) answer++;
                }
                                        
        return answer;
    }
}

음 max값 구하고

에라토스테네스의 체 사용 후 배열 쭉 돌려서 계산