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

문제 컨셉

1,000,000 이하의 큰 수의 소수를 구해야하는 문제이다. 기존의 방법처럼 2 부터 N까지 1씩 증가해가며 모든 수에 대해 탐색해야한다면 시간을 초과하게 된다.

에라토스테네스의 체

고대 그리스의 수학자인 에라토스테네스가 만들어 낸 소수를 찾는 방법이다. N이 소수인지 확인할 때, 2부터 N까지 찾는 것이 아니라, N의 제곱근까지만 찾는 방법이다.

이것이 성립하는 이유는 다음과 같다. 90이란 수가 있다고 가정해보자 1과 자기 자신을 제외한 90의 약수는 다음과 같이 표현할 수 있다.

2 (x45), 3 (x30), 5 (x18), 6 (x15), 9 (x10), 10 (x9), 15 (x6), 18 (x5), 30 (x3), 45 (x2)

여기서 9x10, 10x9를 기준으로 좌우 대칭 형태임을 확인할 수 있는데, 90의 제곱근은 9.487… 이다.

즉 어짜피 약수가 있다면 제곱근보다 큰 수는 제곱근 보다 작은 수의 대칭 형태이므로 제곱근보다 작은 수까지만 계산하여도 해당 수가 소수인지 아닌지 알 수 있다는 것이다.

자료의 수를 n**1/2 만큼 줄이는 알고리즘이라 할 수 있다.

코드

# 1929. 소수 구하기
M, N = map(int,input().split())
def get_prime(num):
    sqrt = int(num ** (1 / 2))
    for n in range(2, sqrt + 1):
        if num % n == 0:
            return False
    else:
        return True

for num in range(M, N+1):
    if num == 1:
        continue
    if get_prime(num):
        print(num)