BOJ 1929번 : 소수 구하기

안녕하세요. 지난 포스팅의 BOJ 11653번 : 소인수분해에서는 반복문을 이용해서 소인수분해를 구현해보았습니다. 오늘은 BOJ 1978번 : 소수 찾기와 BOJ 2581번 : 소수와 동일한 문제이지만 더욱 빠르게 소수를 찾는 방법에 대해서 알아보겠습니다. 

 

 

완벽한 코딩은 존재하지 않습니다. 제가 제출한 코드 역시 마찬가지고 그저 참고만 해주시길 바랍니다. 

 

핵심 포인트

• 기본 구현능력
• 정수론 지식

 

제출 코드

import math

M, N = map(int, input().split())

for n in range(M, N + 1) :
    if n == 1 : continue
    flag = 1
    for i in range(2, int(math.sqrt(n)) + 1) :
        if n % i == 0 : flag = 0; break
    if flag == 1 : print(n)

 

해설

BOJ 1978번 : 소수 찾기와 BOJ 2581번 : 소수와 동일한 문제입니다. 하지만, 더욱 빠르게 소수인지 판별을 해야하죠. 소수를 판별할 때 가장 오래걸리는 부분은 $2 ~ \frac{n}{2}$ 범위의 모든 자연수들을 확인해봐야한다는 점 입니다. 이 범위를 조금이라도 줄일 수 있으면 빠르게 소수인지 알 수 있겠죠? 정수론에서는 이에 대한 답으로 $2 ~ \lfloor\sqrt{n}\rfloor$ 범위의 자연수들만 확인해보면 소수인지 판별할 수 있음이 알려져있습니다. 이를 활용해서 문제를 풀면 더욱 빠르게 소수를 찾을 수 있죠. 

 

참고자료 및 그림출처

백준 코딩 문제