[백준] 1929 소수 구하기 (Baekjoon Problem 1929: Get Prime Number)

문제 출처

[문제 요약]

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

(1 <= M <= N <= 1,000,000)

[풀이]

범위 안의 숫자 중 하나인 n이 소수인지 판단을 naive하게 해보면 n보다 작은 수들로 나누는 것이다.

만일 나누어 떨어지는 수가 있는경우는 소수가 아니고, 없는 경우는 소수라고 판단할 수 있다.

하지만 숫자의 범위가 커서 이 방법으로 하면 시간초과가 뜬다.

 

어떤 수 n의 약수를 생각해보자. 만일 n의 제곱근 이하에서 약수 a가 찾아지면, n의 제곱근 이상에서 n / a = b인 다른 약수가 존재한다. 따라서 n 제곱근 이하에서만 어떤 수의 약수가 있는지를 보면 된다.

이 원리를 에라토스테네스의 체라고 한다 (자세한 설명).

[유의할 점]

조금 더 속도를 빠르게 하고자 2로 처음에 나누어지는지 보고, 에라토스테네스의 체를 적용시킬때 모든 짝수는 건너뛰었다.

이 과정에서 2가 소수인것을 건너뛸때가 있어서 처음 m이 1이고 n이 2 이상일때, 그리고 m이 2 이상일때의 케이스를 따로 분류 시켜두었다.

 

그리고 제곱근을 구할때 모든 범위의 수를 표현하기 위해 ceil 함수를 써준다. ceil은 어떤 수를 올림하는 함수이다. 올림을 하는 이유는 n도 포함되기 때문이다.

[파이썬 3 코드]

# -*- coding: utf-8 -*-
import math

def is_prime(num):
    if num % 2 == 0:
        return False
    else:
        for i in range(3, math.ceil(pow(num, 1/2)) + 1, 2):
            if num % i == 0:
                return False
        return True

if __name__ == "__main__":
    m, n = map(int, input().split())

    if m == 1 and n != 1:
        print(2)
        m += 2
    elif m == 2:
        print(2)
    if m % 2 == 0:
        m += 1
    for i in range(m, n+1, 2):
        if is_prime(i):
            print(i)