[Lv.1] 소수 찾기 [프로그래머스_코딩테스트] [에라토스테네스의 체] [10분]

🔍 문제 요약

https://school.programmers.co.kr/learn/courses/30/lessons/12921

프로그래머스

1에서 n까지의 숫자에서 소수의 개수를 반환하는 문제. (n은 2이상 1000000이하의 자연수)

🧠 나의 접근 방식과 시행착오

9분 정도 걸린 문제. 아무래도 소수를 구하는 거 자체는 어렵지 않기 때문에 최적화로 시간 효율이 얼마나 좋은지를 체크하는 문제다. 다만 필자도 n의 제곱근값 까지 순회를 시켜서 나눌 수 있는 지 체크해서 카운트를 증가시키는 방법으로 풀긴 한거라 더 효율적인 형태가 있을 것이라는 생각은 한다. 다만 전에 본 듯 한데 까먹은..

using System;

public class Solution
{
    /// <summary>
    /// 소수 찾기
    /// https://school.programmers.co.kr/learn/courses/30/lessons/12921
    /// </summary>
    public int solution(int n)
    {
        int count = 0;

        for (int i = 2; i <= n; i++)
        {
            if (CheckNumber(i))
            {
                count++;
            }
        }
        
        return count;
    }

    public bool CheckNumber(int num)
    {
        int routeNum = (int)MathF.Sqrt(num);
        if (num == routeNum)
        {
            routeNum = num - 1;
        }
        
        for (int i = 2; i <= routeNum; i++)
        {
            if (num % i == 0) return false;
        }

        return true;
    }
}

✅ 풀이 코드

피드백으로 나온 것은 일단 routeNum이 num과 같은지 예외처리된 부분인데 사실 이건 의미가 없긴 하다 (1아니면 해당 동작이 되는 수가 없음) 그리고 그 외에는 에라토스테네스의 체를 쓰는 방식인데 아래 코드와 같다. (필자가 푼 방식은 O(n√n)이고 아래 방법은 O(n*log(logn)) 이라고 한다) 대강의 흐름을 보면 작은 수부터 일단 i가 2일 때 isPrime은 true이고 해당 수의 제곱인 4부터 n까지 2씩 증가한 값들은 모두 소수가 아닌 수로 체크해둔다. (제곱한 값과 동일한 i를 더한 값은 배수에 속하기에 당연한 이야기지만 나나눌 수 있는 값이 존재하게 되므로 false로 바꾸는 것으로 보임)

public int solution(int n)
{
    bool[] isPrime = new bool[n + 1];
    Array.Fill(isPrime, true);
    isPrime[0] = isPrime[1] = false;

    for (int i = 2; i * i <= n; i++)
    {
        if (isPrime[i])
        {
            for (int j = i * i; j <= n; j += i)
            {
                isPrime[j] = false;
            }
        }
    }

    int count = 0;
    foreach (bool b in isPrime)
    {
        if (b) count++;
    }
    return count;
}

🔄 정리

소수의 개수를 계산하는 문제에서는 에라토스테네스의 체라는 것을 기억해두면 정말 간단하게 계산을 할 수 있는 것을 보인다. 또는 그 외에 소수를 활용한 무언가를 한다면 유용할 듯한 느낌이다.