[Python] 백준 1929번: 소수 구하기

www.acmicpc.net/problem/1929

1929번: 소수 구하기

import sys
input = sys.stdin.readline


def getIsPrimeNumberList(N):
    isPrimeNumberList = [True]*(N+1)
    isPrimeNumberList[1] = False

    for i in range(2, int(N**(1/2))+1):
        if isPrimeNumberList[i]:
            j = 2
            while i*j <= N:
                isPrimeNumberList[i*j] = False
                j += 1

    return isPrimeNumberList


M, N = map(int, input().split())
isPrimeNumberList = getIsPrimeNumberList(N)
for i in range(M, N+1):
    if isPrimeNumberList[i]:
        print(i)

 

우선, n이 주어졌을 때 2~n까지 for문을 돌면서 나머지가 0이면 소수가 아니다라고 판별하는 풀이는 O(N)로 시간초과가 뜰 것이다.

이에 더 발전된 풀이로, 위 풀이에서 for문을 2~√n까지 도는 것이 있는데, 이것이 유효한 이유는 다음과 같다.

16을 소인수분해하면, 1 2 4 8 16인데, 여기서 √16인 4를 기준으로 4*4, 2*8, 1*16과 같은 형태를 띄고 있으므로 4까지만 조사하면 된다. 이것의 빅오는 O(√N)이다.

 

다만 여기서 더욱 발전된 풀이법이 있다. '에라토스테네스의 체'이다. 기존의 방식의 문제점은, 여러 개의 숫자에 대해서 소수인지를 판별할 때 비효율적이라는 것이다.

가령, input 값에 1 16이 들어왔다고 하자. 4가 소수인지 판별하기 위해 2로 나누어주어야하고, 이후에 8이 소수인지 확인하기 위해 2로 또 다시 나누어줘야 한다는 것이다.

 

따라서, N까지의 숫자들이 소수인지 아닌지를 담는 리스트(isPrimeNumberList)를 하나 만들어준다. 처음에는 모두 True값을 가지고 있다. 이후 for문을 2~√N까지 돌아주는데, 현재 i가 소수(예를 들어, 2)일 경우, 이것을 2부터 계속해서 곱해주면서(2, 4, 6, 8, ... ) isPrimeNumberList의 해당 인덱스 값을 False로 바꿔주는 것이다. 대신, 소수 판별을 N까지만 하면 되므로 조건(i*j <= N)을 걸어준다.

 

여담으로, 꼭 에라토스테네스의 체라는 개념을 몰라도, DP 개념을 접목하면 쉽게 풀 수 있다.