소수 구하기: 백준 1929

에라토스테네스의 체는 $O(nlog(logn))$의 시간 복잡도를 가지는 알고리즘으로, 효율적으로 소수(Prime Number)를 구할 수 있다. 

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

아이디어는 간단하다. 자연수 N이 있을 때, N의 배수는 소수가 아니다. 소수는 1과 자기 자신만을 약수로 가지는데, N의 배수는 N을 약수로 가지기 때문이다. 소수의 정의를 생각해 보면 당연한 이야기이다. 

1 ~ 100까지의 수가 있는 표를 만들자. 그리고 만약 소수가 아니라면 표에서 값을 지운다. 0과 1은 소수가 아니다.

0

1

2

3

4

5

6

7

8

...

2는 소수이다. 하지만 2의 배수는 소수가 아니다. 따라서 4, 6, 8 ... 등은 지운다.

0

1

2

3

4

5

6

7

8

...

3은 소수이다. 하지만 3의 배수는 소수가 아니다. 따라서 6, 9, 12 ... 등은 지운다.

4는 이미 수소가 아님이 밝혀졌다.

5는 소수이다. 하지만 5의 배수는 소수가 아니다...

이렇게 반복하다보면 소수가 아닌 수들은 모두 삭제되고, 소수만 남게 된다. 총 N개의 수가 있다면 N를 모두 살펴볼 필요 없이 $\sqrt{N}$까지 살펴보면 된다. 제곱근을 넘어가는 수의 배수는 이미 앞에서 모두 삭제가 된다. 따라서 제곱근까지만 계산해도 소수가 아닌 수를 모두 지울 수 있다.

이해가 되지 않는다면 6이라는 수를 생각해 보자. 6을 $n \times m$으로 표현하면 아래와 같다.

n	m
1	6
2	3
3	2
6	1

보면 (1 * 6)과 (6 * 1)은 중복이다. (2 * 3)은 (3 * 2)와 중복이다. 이처럼 n이 제곱근을 넘어가면 순서만 바뀐 채로 다시 반복된다. 그렇기 때문에  $\sqrt{N}$까지만 살펴봐도 모든 배수들을 찾아낼 수 있다고 한 것이다. 

---

Python 구현

에라토스테네스의 체를 Python으로 구현해 보자. 원리는 동일하지만 배수를 찾을 때마다 list에서 값을 삭제하기에는 비용이 너무 크다. 따라서 True, False로 이루어진 list를 만들고, 소수가 아니면 False로 표시하는 방법을 사용했다. 

def check_primes(max_range):
    # 모든 수를 소수라고 가정한다.
    is_prime = [True for _ in range(max_range + 1)]
    # 0과 1은 소수가 아니다.
    is_prime[0] = False
    is_prime[1] = False

    # 최댓값의 제곱근을 구한다.
    sqrt = int(max_range**0.5)
    for i in range(2, sqrt + 1):
        # i가 소수라면, i의 배수는 False로 처리한다.
        if is_prime[i]:
            j = 2
            while i * j <= max_range:
                is_prime[i * j] = False
                j += 1
    # 소수면 해당 index에 True가 담긴 list를 반환한다.
    return is_prime

 

---

백준 1929 (Python, Go 풀이)

1929번: 소수 구하기

문제: M이상 N이하의 소수를 모두 출력하는 프로그램을 작성하시오.

[ 입력 ]
3 16

[ 출력 ]
3
5
7
11
13

 

Python으로 구현했던 내용을 이용해보자. 

import sys

input = sys.stdin.readline
print = sys.stdout.write

def check_primes(max_range):
    is_prime = [True for _ in range(max_range + 1)]
    is_prime[0] = False
    is_prime[1] = False

    sqrt = int(max_range**0.5)
    for i in range(2, sqrt + 1):
        if is_prime[i]:
            j = 2
            while i * j <= max_range:
                is_prime[i * j] = False
                j += 1
    return is_prime


def solution():
    min_, max_ = input().rstrip("\n").split()
    min_, max_ = int(min_), int(max_)
    is_prime = check_primes(max_)

    for n in range(min_, max_ + 1):
        if is_prime[n]:
            print(f"{n}\n")

    
solution()

Pypy3로 실행하니 172ms, 122664KB가 걸린 풀이이다. 최댓값까지 모든 수에 대하여 True / False를 기록하기 때문에 메모리를 많이 사용하게 된다. 하지만 빨랐죠?

 

Golang으로 풀이해봤더니 확실히 빠른 속도를 체감할 수 있었다. 

package main

import (
	"bufio"
	"fmt"
	"math"
	"os"
	"strings"
	"strconv"
)

var sc = bufio.NewScanner(os.Stdin)
var b strings.Builder

func main() {
	sc.Scan()       
	input := strings.Split(sc.Text(), " ")
	minRange, _ := strconv.Atoi(input[0])
	maxRange, _ := strconv.Atoi(input[1])

	allPrimes := GetPrimeNum(maxRange)[minRange-1:]
	for idx, isPrime := range allPrimes {
		if isPrime {
			b.WriteString(strconv.Itoa(idx + minRange))
			b.WriteString("\n")
		}
	}
	fmt.Print(b.String())
}

func GetPrimeNum(maxRange int) []bool {
	isPrime := make([]bool, maxRange)
	for idx, _ := range isPrime {
		isPrime[idx] = true
	}
	isPrime[0] = false

	sqrt := int(math.Sqrt(float64(maxRange)))
	for i := 2; i <= sqrt; i++ {
		if isPrime[i-1] {
			for j := 2; j*i <= maxRange; j++ {
				isPrime[i*j-1] = false
			}
		}
	}
	return isPrime
}

Python과 같은 원리로 풀이했더니 20ms가 걸렸다.