[BOJ][⚪2][백준#01929] 소수 구하기

문제 출처

BAEKJOON Online Judge #1929

문제

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

입력

첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다.

출력

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

예제

입력

3 16

출력

3
5
7
11
13

My Sol A

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

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

    n = 2
    while (num > n) and (num % n != 0):
        n += 1

    if n == num:
        print(num)

결과

시간 초과

효율적인 코드라고 생각했는데 왜일까. 아마도 while문을 사용하였기 때문에 종료 조건이 무언가 잘못되었나보다.

My Sol B

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

for num in range(M, N+1):
    cnt = 0
    for n in range(1, num+1):
        if cnt > 2:
            break

        if num % n == 0:
            cnt += 1
            continue

    if cnt == 2:
        print(num)

for문을 사용했다. 약수의 개수를 cnt로 세고 조회하는 숫자 그 자체까지 cnt를 늘려가는데 cnt가 2를 넘긴, 즉 소수가 아니면 바로 for문을 종료하고 cnt가 2인지를 확인하여 2라면 num을 print하는 반복문으로 간다.

소수라면 1부터 자기 자신까지 조회하므로 cnt는 2일 것이고 조건문에 부합하므로 num을 출력하고 다음 num의 반복을 시작한다.

결과

시간 초과

뭐가 문제인걸까? cnt가 2인지를 확인하는 조건문보다는 1과 자기 자신을 제외한 숫자 영역에서 약수가 발견되면 바로 반복을 종료하는 로직이 시간을 확실히 덜 수 있을 것이다. 그런데 그것은 Sol A와 같은 방식이다. Sol A도 시간 초과가 발생했다.

오랜 고민에도 이유를 모르겠다. 도저히 모르겠어서 답안을 찾아보았다.

모범답안

출처

x, y = map(int, input().split())

for i in range(x, y+1):
    if i == 1:
        continue
    for j in range(2, int(i** 0.5)+1 ):
        if i%j==0:
            break
    else:
        print(i)

이 방법이 특이한 이유는 제곱근에 있다. M과 N 사이의 수에 대해 2부터 N의 제곱근까지의 수의 배수로만 조회하는 것이다.

그 이유는 약수는 대칭으로 이루어져 있기 때문이다. 즉, 제곱근까지가 소수의 약수를 조회해야하는 최대의 값이라는 것이다. 예를 들어 900은 30**2 인데 899의 소수 여부를 확인하기 위해서는 제곱근의 ceil값인 30까지만 조회하면 된다는 것이다. 여기까지 약수가 없다면 그 이후에도 약수가 있을 수가 없다.

다른 방법으로는 에라토스테네스의 체라는 방식을 활용한다. 이는 일정 범위 내의 수열에서 배수들을 제거하면서 소수만 남기는 방법이다. 이 부분은 algorithm 파트에서 따로 다루려고 하므로 아래 링크를 참고하면 되겠다.

소수 구하기