[단계별로 풀어보기] [python3] 기본 수학 2 - 소수 구하기 (1929)

1929번: 소수 구하기 (acmicpc.net)

1929번: 소수 구하기

첫 제출

소수의 정의는 1과 자기 자신을 제외한 나머지 수로 나누어지지 않는 수를 의미하므로

각 수의 제곱근까지 for문을 돌려서 소수인지를 판별했다.

(제곱근까지 나누는 이유는 n의 약수는 n의 제곱근보다 같거나 작기 때문이다)

import math

m, n = map(int, input().split())
for i in range(m,n+1):
    isSo = True
    if i == 1:
        isSo = False
    for k in range(2, int(math.sqrt(i))+1):
        if (i % k) == 0:
            isSo = False
    if isSo == True:
        print(i)

시간 초과로 실패.

시간복잡도가 O(n^2)이므로 실패한 듯 하다.

이를 해결하기 위해 에라토스테네스의 체를 이용했다.

최종 제출

최대 숫자인 m만큼의 Boolean 리스트를 만든 후, 소수만 True로 남기고 나머지는 False로 지정한다.

이제 주어진 숫자들이 해당 Boolean 리스트에서 True인지를 판별하면 소수 여부를 가릴 수 있다.

def isSosu(m, n):
    n += 1
    trueArr = [True] * n
    for i in range(2, int(n**0.5)+1):
        if trueArr[i]:
            for j in range(2*i, n, i):
                trueArr[j] = False
                
    for i in range(m, n):
        if i> 1 and trueArr[i] == True:
            print(i)

m, n = map(int, input().split())
isSosu(m, n)