1. 소수 판별

여기서부터는 문법이 아니라 알고리즘입니다. 그런데 겁먹을 필요 없어요. 알고리즘의 8할은 "무식하게 다 해보기(완전탐색)"에서 시작해서 "똑똑하게 줄이기(최적화)"로 발전시키는 것이고, 소수 판별이 그걸 배우기에 가장 좋은 첫 문제입니다.

이 한 챕터에서 배우는 것:

• 완전탐색으로 문제를 먼저 푸는 법
• 시간복잡도(Big-O) 가 뭔지 감 잡기
• 같은 문제를 반복문 하나로 확 빠르게 만드는 법 (√n 최적화)
• 여러 수를 한 번에 처리하는 에라토스테네스의 체

소수가 뭐였죠?

1과 자기 자신으로만 나누어지는, 1보다 큰 자연수. (2, 3, 5, 7, 11, 13, ...)

1은 소수가 아니고, 2는 유일한 짝수 소수입니다.

1단계: 무식하게 다 해보기 (완전탐색)

"n이 소수인가?"를 정의 그대로 옮기면 됩니다. 2부터 n-1까지 하나씩 나눠보고, 하나라도 딱 나누어떨어지면 소수가 아니다.

def is_prime(n):
    if n < 2:              # 1 이하는 소수가 아님
        return False
    for i in range(2, n):  # 2, 3, ..., n-1 로 나눠보기
        if n % i == 0:     # 나누어떨어지면 = 약수를 찾았으면
            return False   # 소수가 아니다
    return True            # 끝까지 약수가 없었으면 소수다

print(is_prime(7))    # True
print(is_prime(12))   # False  (2로 나누어짐)
print(is_prime(1))    # False

💡 return False가 반복문 안에서 나오는 순간 함수는 바로 끝납니다. 약수를 하나라도 찾으면 더 볼 필요가 없으니 즉시 탈출하는 거예요. 이게 반복문 최적화의 기본 감각입니다.

잠깐, 이게 얼마나 느릴까?

is_prime(n)은 최악의 경우 약 n번 반복합니다. n이 소수라면 끝까지 다 돌아야 하니까요.

• n = 100 → 약 100번
• n = 1,000,000 → 약 100만 번
• n = 1,000,000,000 → 약 10억 번 😱

"입력이 커질수록 몇 번 일하나"를 대충 표현한 게 시간복잡도이고, 이걸 O(n) (오 엔) 이라고 씁니다. 위 코드는 O(n) 입니다.

💡 코딩테스트에서 "시간 초과"가 나면 대부분 이 시간복잡도가 너무 큰 겁니다. 보통 컴퓨터는 1초에 약 1억 번 연산합니다. 10억 번짜리 O(n)이면 시간 초과인 거죠.

2단계: 똑똑하게 줄이기 (√n 최적화)

핵심 관찰: 약수는 항상 짝을 지어 나온다.

36의 약수를 보면: 2 × 18, 3 × 12, 4 × 9, 6 × 6, 9 × 4, ... 6(=√36)을 기준으로 대칭입니다. 그래서 √n까지만 확인해서 약수가 없으면, 그 뒤로도 없습니다.

즉 2부터 √n까지만 나눠보면 됩니다.

def is_prime(n):
    if n < 2:
        return False
    i = 2
    while i * i <= n:      # i * i <= n  는  i <= √n  과 같은 말 (제곱근 계산 없이!)
        if n % i == 0:
            return False
        i += 1
    return True

print(is_prime(97))    # True
print(is_prime(1000000007))  # True  (이제 이 큰 수도 순식간에!)

i * i <= n은 i <= √n과 같습니다. 제곱근을 직접 구하면 실수 오차가 생길 수 있어서, 양변을 제곱한 i * i <= n 형태를 즐겨 씁니다.

이제 반복 횟수는 약 √n번. 이걸 O(√n) 이라고 합니다.

• n = 1,000,000,000 → 약 √10억 ≈ 31,623번 (10억 번 → 3만 번으로!)

💡 같은 문제, 같은 답. 바뀐 건 반복 범위 하나뿐인데 성능이 3만 배 빨라졌습니다. "무식한 풀이 → 관찰 → 범위 줄이기" 이 흐름이 알고리즘 공부의 전부라고 해도 과언이 아닙니다.

3단계: 여러 수를 한 번에, 에라토스테네스의 체

"n이 소수인가?" 하나면 √n으로 충분합니다. 그런데 "1부터 N까지 소수를 전부 구하라" 면 이야기가 달라집니다. 하나하나 is_prime을 부르면 느려요.

발상을 뒤집습니다. 소수를 찾는 게 아니라, 소수가 아닌 것(배수)을 지워나갑니다.

1. 2부터 N까지 다 소수 후보로 둔다.
2. 2의 배수(4, 6, 8, ...)를 전부 지운다.
3. 3의 배수(6, 9, 12, ...)를 전부 지운다.
4. 다음 안 지워진 수(5)의 배수를 지운다... 반복.
5. 끝까지 안 지워지고 살아남은 수가 소수다.

이걸 자료구조로 표현합니다. 여기서 리스트(불리언 배열) 가 핵심 도구예요.

def sieve(N):
    # is_prime[i] = i가 소수인가? 일단 전부 True로 시작
    is_prime = [True] * (N + 1)
    is_prime[0] = is_prime[1] = False   # 0과 1은 소수 아님

    i = 2
    while i * i <= N:               # 여기서도 √N 까지만!
        if is_prime[i]:             # i가 아직 안 지워졌으면
            for j in range(i * i, N + 1, i):   # i*i부터 i씩 뛰며
                is_prime[j] = False            # i의 배수를 전부 지움
        i += 1

    # 살아남은 인덱스만 모으면 소수 목록
    return [i for i in range(2, N + 1) if is_prime[i]]

print(sieve(30))
# [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]

두 가지 작은 최적화가 들어있어요:

• 바깥 반복도 i * i <= N까지만 (√N 최적화 재등장)
• 지우기 시작점을 i * 2가 아니라 i * i부터 (그 앞의 배수들은 더 작은 수가 이미 지웠으니까)

💡 리스트를 "값을 저장하는 상자"가 아니라 "체크 표시하는 칠판" 으로 쓰는 이 발상이 자료구조 활용의 시작입니다. [True] * (N+1)로 인덱스를 곧 숫자 자체로 쓰는 패턴, 앞으로 아주 자주 만납니다.

집합(set)으로 빠른 소수 확인표 만들기

체로 구한 소수 목록을 집합에 넣으면, "이 수가 소수야?"를 즉시(O(1)) 확인할 수 있습니다.

primes = set(sieve(100))     # {2, 3, 5, 7, 11, ...}

print(41 in primes)   # True
print(42 in primes)   # False

리스트로 41 in primes를 하면 처음부터 훑지만(O(n)), 집합은 거의 즉시 찾습니다. "포함 여부를 자주 물어볼 때는 set" — 이것도 자료구조 감각입니다.

정리

💡 문제를 만나면 ① 무식하게라도 일단 풀고 → ② 시간복잡도를 따져보고 → ③ 관찰로 범위를 줄이거나 자료구조를 바꾼다. 이 세 단계가 모든 알고리즘 문제에 통하는 사고 틀입니다. 소수는 그 첫 연습이었어요.

직접 풀어보기

1. is_prime(√n 버전)을 이용해 1부터 100까지 소수의 개수를 세보세요. (정답: 25개)
2. sieve(N)로 1부터 1000까지 소수의 합을 구해보세요.
3. 두 소수의 합으로 나타낼 수 있는 짝수를 찾아보세요. (예: 10 = 3 + 7) — 체로 만든 소수 집합을 활용하면 쉽습니다.