백준 1978, 1929 문제 풀이: 소수 판별 알고리즘

🔢 소수란?

소수는 1과 자기 자신만을 약수로 가지는 수.

📌특징

• 1은 소수가 아니다.
• 2는 유일한 짝수 소수이다.

---

📌판별 알고리즘

소수를 하나 판별할 때와, 여러 개 판별할 때로 나눌 수 있다.

1️⃣ 하나의 수가 소수인지 판별하는 방법

✔️ 약수의 성질 활용

• N을 반으로 나눈 값(제곱근)까지 N으로 나누어떨어지는 수가 있는지 확인한다.
• 나누어떨어지면 소수가 아니다.

import math

def is_prime(n):
    if n < 2:  # 1은 소수가 아님.
        return False
    for i in range(2, int(math.sqrt(n)) + 1):
        if n % i == 0:
            return False
    return True

2️⃣ 범위 내 여러 개 소수 판별 방법

✔️ 에라토스테네스의 체 알고리즘 활용

• 2부터 범위까지 나오는 소수의 배수를 지워간다.
• 예시: 2의 배수 2*i, 다음 3, 다음 5 이런 식으로 제거한다.

def sieve_of_eratosthenes(limit):
    
    is_prime = [True] * (limit + 1)  # 처음 모든 수를 소수로 가정
    is_prime[0], is_prime[1] = False, False  # 0, 1 은 소수가 아님.

    for num in range(2, int(limit ** 0.5) + 1):
        if is_prime[num]:
            for multiple in range(num * num, limit + 1, num):
                is_prime[multiple] = False

    return is_prime

---

알게된 점

소수 문제를 풀 때 제곱근과 에라토스테네스의 체를 활용하면 계산량을 줄일 수 있다.