[파이썬/Python] 백준 1978번 소수 찾기

[파이썬/Python] 백준 1978번 소수 찾기

1978번: 소수 찾기

---

문제

주어진 수 N개 중에서 소수가 몇 개인지 찾아서 출력하는 프로그램을 작성하시오.

입력

첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다.

출력

주어진 수들 중 소수의 개수를 출력한다.

 

예제 입력

4
1 3 5 7

예제 출력

3

풀이 1

에라토스테네스의 체

import sys

def get_primes(n):
    # 0과 1은 소수가 아니므로, False 처리
    is_prime = [False, False] + [True] * (n-1)
    primes = []
    # 2부터 n까지의 수에 대해서, 에라토스테네스의 체 알고리즘 적용
    for i in range(2, n+1):
        if is_prime[i]:
            primes.append(i)
            # i의 배수들은 소수가 아니므로 False 처리
            for j in range(i*2, n+1, i):
                is_prime[j] = False
    return primes

# 입력값 처리
sys.stdin.readline()
lst = list(map(int, sys.stdin.readline().split()))

# lst의 최대값까지의 소수 리스트를 구함
primes = get_primes(max(lst))

cnt = 0
# lst에서 소수의 개수를 구함
for i in range(len(lst)):
    if lst[i] in primes:
        cnt += 1

print(cnt)

get_primes 함수는 에라토스테네스의 체 알고리즘을 이용하여 n 이하의 소수를 모두 찾아서 리스트로 반환한다. 에라토스테네스의 체는 2부터 시작하여 배수를 지우면서 남은 수들이 소수임을 이용한다. 따라서 is_prime 리스트는 0과 1을 제외하고 True로 초기화한 후, 2부터 n까지의 수에 대해서 에라토스테네스의 체를 적용한다. 즉, is_prime[i]가 True이면 i는 소수이므로 primes 리스트에 추가하고, i의 배수들을 False 처리한다.

lst 리스트는 sys.stdin.readline().split() 함수를 이용하여 입력된 값을 리스트로 변환한 것이다. 입력값의 첫번째 라인은 무시하고, 두번째 라인에서 입력값을 받는다.

max(lst)를 이용하여 입력값 중에서 가장 큰 수를 찾은 후, get_primes 함수를 이용하여 이 수까지의 소수 리스트를 구한다. 이후 cnt 변수를 0으로 초기화한 후, lst 리스트에서 소수의 개수를 찾는다. 이때 in 연산자를 이용하여 해당 수가 소수 리스트에 있는지 검사한다. 소수 리스트는 이미 구해놓았으므로, 검사하는 시간을 줄일 수 있다.

 

풀이 2

제곱근까지 검사

import sys

# 입력값 처리
sys.stdin.readline()
lst = list(map(int, sys.stdin.readline().split()))

cnt = 0
# lst에서 소수의 개수를 구함
for i in lst:
    if i < 2: continue # 1보다 작은 값은 소수가 아니므로 제외
    for j in range(2, int(i ** 0.5) + 1):
        if i % j == 0: break # 나누어 떨어지면 소수가 아니므로 종료
    else: cnt += 1 # for문이 끝까지 돌면 소수이므로 cnt를 증가

print(cnt)

주어진 코드에서는 입력값 처리와 소수 구하는 부분이 간단해졌다. 입력값의 첫번째 라인은 무시하고, 두번째 라인에서 입력값을 받는다. 소수를 구하는 부분에서는 get_primes 함수를 사용하지 않고, for 반복문과 if 조건문을 이용하여 해당 수가 소수인지 검사한다.

입력값에서 두번째 라인을 처리한 후, lst 리스트에 저장한다. 이후 cnt 변수를 0으로 초기화한 후, lst 리스트에서 소수의 개수를 찾는다. 이때 if i < 2: continue 코드를 이용하여 1보다 작은 값은 소수가 아니므로, 검사하지 않는다. 그리고 for 반복문과 if 조건문을 이용하여 해당 수가 소수인지 검사한다. range(2, int(i ** 0.5) + 1) 구문에서는 해당 수의 제곱근까지만 검사하면 되므로, 불필요한 계산을 줄일 수 있다. 소수가 아닌 경우 break 구문을 이용하여 반복문을 종료한다. 그리고 for 반복문이 끝까지 실행되면 해당 수는 소수이므로 cnt 변수를 증가시킨다.

이 코드의 장점은 간단한 구현과 속도가 빠르다는 것이다. 그러나 에라토스테네스의 체 알고리즘보다는 비교적 느리며, 큰 수에 대해서는 속도가 느려질 수 있다.

 

참고자료

두번째 코드에서 사용된 for else 문은 존재를 처음 알게 되었다. 상당히 유용하게 사용할 것 같다.

Python :: for else 문 사용법