TIL: 단일 숫자 소수 판별과 에라토스테네스의 체

단일 숫자 소수 판별 (√N까지만 검사)

• 어떤 자연수 N이 소수인지 확인할 때, 2부터 √N까지만 나눠보면 충분.
• 이유: N이 합성수라면 반드시 √N 이하의 약수를 가짐.
• 예시: N = 14 → 2와 3만 검사하면 충분.

public bool IsPrime(int n)
{
    if (n < 2) return false; // 0, 1은 소수가 아님

    for (int i = 2; i * i <= n; i++)
    {
        if (n % i == 0) return false;
    }

    return true;
}

• 시간 복잡도: O(√N)
• 핵심 포인트: 0, 1 처리, 나누어 떨어지면 합성수 판정, √N까지만 검사

에라토스테네스의 체 (범위 내 모든 소수 구하기)

• 2부터 N까지의 모든 소수를 한 번에 구하는 방법.
• 핵심 아이디어:

• 1. 2부터 N까지 숫자 리스트 생성
  2. 2 제외한 2의 배수를 모두 제거
  3. 리스트에서 다음 남은 수(3) 선택, 3의 배수 제거
  4. 이 과정을 √N 이하 수까지 반복
• 결과: 리스트에 남은 수가 모두 소수

예시: N = 14

1. 처음 리스트: 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14
2. 2의 배수 제거 → 2, 3, 5, 7, 9, 11, 13
3. 3의 배수 제거 → 2, 3, 5, 7, 11, 13
4. √14 ≈ 3.74 → 여기서 종료, 남은 수가 소수: 2, 3, 5, 7, 11, 13
   C# 코드 예시

bool[] Sieve(int n)
{
    bool[] isPrime = new bool[n + 1];
    for (int i = 2; i <= n; i++) isPrime[i] = true;

    for (int i = 2; i * i <= n; i++)
    {
        if (isPrime[i])
        {
            for (int j = i * i; j <= n; j += i) //i의 모든 배수
            {
                isPrime[j] = false;
            }
        }
    }
    return isPrime;
}

• 시간 복잡도: O(N log log N)
• 장점: 범위 내 모든 소수를 효율적으로 구할 수 있음
• 핵심 포인트: 2부터 시작, √N까지만 배수 제거, 남은 수가 소수

나만의 단어로 정리하기

• 단일 소수판별 = √N까지만 탐색하여 i와 나눠지는 숫자가 없다면 N == Prime
• 범위 내의 소수 판별 = N 범위 안의 2를 초과하는 모든 숫자의 배수를 소수에서 제외해준다