본문 바로가기

HOW/BaekJoon

[BaekJoon] #1929 소수 구하기 | 백준 파이썬(python) 풀이 및 접근방법

문제

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

 

첫째 줄에 자연수 M과 N이 빈칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000)

 

한 줄에 하나씩, 증가하는 순서대로 소수를 출력한다.

 


접근

1부터 n까지의 수 중에서 소수가 무엇인지 알아보기 위해선 2의 배수부터 n의 배수를 모두 지우면 됩니다.

이러한 방법은 무척이나 정확하나 무척이나 오래 걸립니다.

만약 이러한 방법을 이용해서 풀이하셨다면 '시간 초과'라고 표시되는 것을 보셨을 겁니다.

그럼 이러한 시간을 줄이는 방법이 뭐냐? 바로 에라토스테네스의 체입니다.

 

에라토스테네스가 누구길래 그 사람의 체를 알아야 하냐고 말씀하실 수 있습니다.

에라토스테네스는 중학생과 친한 철학자라고 말할 수 있겠습니다.

중1 수학에서는 '소수'에 대한 개념을 설명할 때 등장하고 중2 과학에선 '지구의 둘레 측정'에서 등장합니다.

옛날 치고는 무척이나 정확한 둘레의 값을 측정한 것으로 유명하죠.

 

여하튼 인물 소개는 끝났으니 에라토스테네스의 체에 대해 알아보겠습니다.

1~50까지의 수 중에서 소수를 찾겠다고 한다면 그 수가 본인 말고 다른 수로 나누어지는지 확인하면 됩니다.

50의 경우 2로 나누어지니 빼고, 49를 기준으로 생각한다면 7 * 7이라는 것을 알 수 있습니다.

즉 소수가 아닌 수는 7 이하의 수로 나누어진다는 것을 알 수 있습니다.

 

다시 말해 1부터 n까지의 수 중에서 m이 소수인지 확인하려면

m이 $\sqrt{n}$ 이하의 수로 나누어지는지 확인하면 됩니다.

 

def check(i):
    if i < 2:
        return False
    if i == 2 or i == 3:
        return True
    if i % 2 == 0 or i % 3 == 0:
        return False
    ii = int(i ** 0.5) + 1
    for iii in range(5, ii, 2):
        if i % iii == 0:
            return False
    return True

이러한 내용을 함수로 만들면 위와 같습니다.

i로 받은 수가 1 혹은 그 이하인지 아닌지 확인하기 위해 우선 $i < 2$ 인지 확인합니다.

만일 1 초과일 경우 2이거나 3인지 확인합니다.

그것도 아니라면 2나 3으로 나누어지는지 확인합니다. 이러한 과정을 통해 시간을 절약합니다.

 

만일 이러한 과정을 모두 통과하였다면 ii에 $\sqrt{i}$를 저장합니다.

그 뒤 iii에 ii까지의 수를 대입하기 위해 range를 활용하는데 2와 3은 앞서 점검했으니

5부터, 2개씩 대입하도록 합니다.

 

그뒤 만일 i가 iii로 나누어질 경우 소수가 아닌 것으로 출력합니다.

이러한 과정을 모두 통과하였다면 소수로 출력합니다.


풀이

def check(i):
    if i < 2:
        return False
    if i == 2 or i == 3:
        return True
    if i % 2 == 0 or i % 3 == 0:
        return False
    ii = int(i ** 0.5) + 1
    for iii in range(5, ii, 2):
        if i % iii == 0:
            return False
    return True


n_min, n_max = list(map(int, input().split()))
for n in range(n_min, n_max + 1):
    if check(n):
        print(n)

풀이 코드는 위와 같습니다.

우선 최솟값과 최댓값을 int로 입력받습니다.

그 후에 range를 활용하여 최소값 이상, 최대값 이하의 수를 하나하나 받아옵니다.

 

range를 이용하여 n에 수를 받아오면 소수인지 판별하는 check에 넣고 소수면 n을 출력하고 아니면 하지 않습니다.

이렇게 한다면 속도가 무척이나 절약됩니다.

 


마무리

이번 문제는 에라토스테네스의 체를 이해하고 있느냐 아니냐로 정답 여부가 갈릴 수 있었던 문제였습니다.

물론 앞선 소수 문제는 체의 개념을 모르고 있더라도 괜찮았었으나 대부분의 대회 문제에서 소수 검산을 필요로 할 시

이번 문제처럼 체를 활용해 최대한 빠르게 소수 검산을 진행하도록 구현되어 있기에

반드시 한 번 짚고 넘어가야 하는 문제였습니다.

 

본 문제의 출처는 백준입니다.