알고리즘 문제

public class Solution 
{
    public int solution(int n) 
    {
        // 1부터 n까지의 소수를 구하기 위한 배열
        // isPrime[i]가 true이면 i는 소수이고, false이면 소수가 아님
        bool[] isPrime = new bool[n + 1];

        // 0과 1은 소수가 아니므로 false로 설정
        isPrime[0] = isPrime[1] = false;
        
        // 2부터 n까지 모든 숫자를 소수로 가정 (기본값을 true로 설정)
        for (int i = 2; i <= n; i++) 
        {
            isPrime[i] = true;
        }

        // 에라토스테네스의 체: 2부터 n까지 숫자 중 소수인 수들의 배수는 소수가 아니므로 false로 설정
        for (int i = 2; i * i <= n; i++) 
        {
            // 만약 i가 소수라면, i의 배수를 모두 소수가 아니라고 표시
            if (isPrime[i]) 
            {
                // i*i부터 시작해서 i의 배수들을 모두 false로 설정
                // i*i부터 시작하는 이유는 그 이전에 나오는 배수들은 이미 이전 숫자에서 처리되었기 때문
                for (int j = i * i; j <= n; j += i) 
                {
                    isPrime[j] = false; // j는 소수가 아니므로 false로 설정
                }
            }
        }

        // 소수의 개수를 세기
        int answer = 0;
        // 2부터 n까지 확인하면서 소수인 경우에만 count 증가
        for (int i = 2; i <= n; i++) 
        {
            if (isPrime[i]) 
            {
                answer++; // 소수일 경우 answer를 1 증가시킴
            }
        }

        return answer; // 최종적으로 소수의 개수를 반환
    }
}

해석

1. bool[ ] isPrime 배열:
   • 이 배열은 각 숫자가 소수인지 아닌지를 나타내는 배열. isPrime[i]가 true라면 i는 소수이고, false라면 소수가 아님.
2. 초기화:
   • isPrime[0]과 isPrime[1]은 소수가 아니므로 false로 설정.
   • 2부터 n까지의 모든 숫자는 처음에 모두 소수라고 가정하여 true로 설정.
3. 에라토스테네스의 체:
   • i가 소수라면, i*i부터 시작해서 i의 배수들을 모두 false로 설정. 왜 i*i부터 시작하는지에 대해서는, i*i 이전의 배수들은 이미 이전 숫자들에 의해 처리되었기 때문.
4. 소수 개수 세기:
   • isPrime[i]가 true인 숫자만 소수이므로, 2부터 n까지 순차적으로 확인하면서 소수라면 answer를 증가.
5. 결과 반환:
   • 마지막으로 소수의 개수를 반환.