[에라토스테네스의 체 / python] 백준 1978. 소수 구하기

https://www.acmicpc.net/problem/1929

1929번: 소수 구하기

 

소수를 구할 때, 그 정의에 따라 우리는 아래 식을 쉽게 떠올릴 수 있다.

def is_prime(n):
    for i in range(2,n):
        if n % i == 0:
            return False
    return True

trash = input()
li = list(map(int, input().split()))
ans = 0
for i in li:
    if i == 1: pass
    elif is_prime(i):
        ans += 1
print(ans)

 

하지만 위 식은 is_prime 함수가 갖는 loop문의 종착지가 n이므로 시간복잡도가 O(n)이라는 것을 유념해야 한다. 따라서 n의 범위가 조금만 커져도 timeout에 걸릴 확률이 높은 것이다.

 

소수의 정의를 잘 생각해볼 때, 그 원리를 이용하여 소수를 구하는 것을 좀 더 빠르게 구현한 알고리즘이 에라토스테네스의 체 알고리즘이다. 소수를 구하기 위해서는 브루트포스를 이용하여 약수가 있는지를 확인하는 것이 가장 간단하지만, 잘 생각해보면 약수는 일종의 좌우대칭(?) 구조이므로 한 쪽의 약수를 구하면, 그 수를 뒤집은 관계의 수는 구할 필요가 없는 것이다. 따라서 절반까지만 구해도 되는 결론이 나오고, 절반씩 줄어드므로 O(logN)을 갖는다.

 

def is_prime_fast(n):
    if n == 1: return False
    for i in range(2, round(n**0.5)+1):
        if n % i == 0:
            return False
    return True


trash = input()
li = list(map(int, input().split()))
ans = 0
for i in li:
    if is_prime_fast(i):
        ans += 1
print(ans)

위 풀이에서 주의할 점은, `round(n**0.5) + 1을 마지막 지점으로 해야한다는 것이다. 반올림이든, 버림이든 어차피 범위 목적상 +1을 해줘야 하니 round() 대신 int()를 사용해도 무방하다.