[Python] 1929-소수 구하기

출처: www.acmicpc.net/problem/1929

1929번: 소수 구하기

결과

풀이 1번 (제곱근 활용)

def isPrime(num):
    if num == 1 : return False

    root = int(num ** .5)
    for k in range(2, root+1):
        if num % k == 0:
            return False
    return True

M, N = map(int, input().split())
for n in range(M, N+1):
    if isPrime(n):
        print(n)

풀이 2번 (에라토스테네스의 체 활용)

def get_primes(m, n):
    sieve = [True] * (n+1)
    sieve[1] = False 
    k = int(n ** .5)
    
    for i in range(2, k+1):
        if sieve[i]:
            for j in range(i+i, n+1, i):
                sieve[j] = False
    return [w for w in range(m, n+1) if sieve[w]]
 
M, N = map(int, input().split())
S = get_primes(M, N)
 
for s in S:
    print(s)

분석
 - 1은 소수가 아닌데 이를 고려하지 않아서 틀렸다.
   난이도가 쉬운 문제임에도 코드가 잘못된 줄 알고 조마조마했다.
 - 풀이 1번(제곱근 활용)에 비해 풀이 2번(에라토스테네스의 체 활용)의 효율이 훨씬 좋았다 (약 10배 정도..)
   시간제한이 엄격한 문제에서는 에라토스테네스의 체를 활용해야겠다