백준 파이썬 1929번

https://www.acmicpc.net/problem/1929

소수를 구하는 방법을 알아보자.

1. N의 제곱근

어떤 자연수는 그 자연수의 두 약수의 곱으로 나타낼 수 있다. 12를 예로 들어보자.
12 =
1 x 12 =
2 x 6 =
3 x 4 =
4 x 3 =
6 x 2 =
12 x 1

즉, 자연수를 두 약수의 곱으로 나타내면 한 약수는 제곱근 보다 적은 수, 다른 약수는 제곱근 보다 큰 수가 된다.
(단, 약수 a, b가 서로 다른 수일 때)

따라서, 어떤 수가 주어졌을 때 그 수가 소수인지 아닌지 알고 싶다면 2부터 그 수의 제곱근보다 작거나 같은 자연수까지 나누었을 때 모두 나머지가 0이 아니면 된다.
글로 쓰니까 어렵네.. 코드를 봐보자

import math
import sys

def is_prime(num: int) -> bool:
    if num == 1:
        return False
    # 2부터 제곱근보다 작거나 같은 수까지 나누어보기
    for j in range(2, int(math.sqrt(num)) + 1):
    	# 나누었는데 나머지가 0이다? => 소수가 아니다
        if num % j == 0:
            return False
    # 다 나누었는데 나머지가 0인적이 없으면 소수
    return True


m, n = map(int, input().split())
#반복문으로 소수 판별 실행
for i in range(m, n+1):
    if is_prime(i):
        sys.stdout.write(str(i) + '\n')

이 코드는 검사할 숫자마다 2부터 제곱근보다 작거나 같은 수까지 나누는 연산을 하기 때문에 검사할 숫자가 커질수록 반복문의 연산도 많아진다.
실행 시간을 줄일 수 있는 방법이 없을까?

2. 에라토스테네스의 체

위 그림처럼 진행되는데 과정은 다음과 같다.

먼저, 2의 배수를 소거한다.

소거된 후 남은 수 중에서 가장 작은 수의 배수를 또 소거한다.(2의 배수가 완료되면 3이 진행된다.)

이를 반복한다.

import sys
import math

MAXNUM = 1_000_000


def is_prime(first: int, end: int):
	
    # 소수를 기록하는 check배열. True면 소수다.
    # 0, 1은 False로 초기화
    check = [False, False] + [True] * MAXNUM
    
    # 2부터 시작해서 배수 소거
    for i in range(2, int(math.sqrt(MAXNUM)) + 1):
        if check[i]: 	
            #
            cnt = 2
            while cnt * i <= end:
                check[cnt * i] = False
                cnt += 1
    # 출력
    for j in range(first, end + 1):
        if check[j]:
            sys.stdout.write(str(j) + '\n')


m, n = map(int, input().split())
is_prime(m, n)

방법 1보다 실행 시간이 많이 단축된 것을 알 수 있다.
배수를 소거할 때마다 소수를 검사할 숫자의 개수가
줄어들기 때문이다.