(Python) 백준 1978번 - 소수 찾기

문제 링크 : https://www.acmicpc.net/problem/1978

1978번: 소수 찾기

풀이

처음엔 단순하게 에라토스테네스의 체 방식으로 풀어서는 시간 초과가 날 수 있을거 같았으나 문제 분류에 에라토스테네스의 체라고 적혀있어서 시도해보았더니 제한 시간 내에 통과할 수 있었다.

n = int(input())
count = 0 # 소수가 아닐 경우를 count
arr = list(map(int, input().split()))
for num in arr:
    if num == 1:  # 1은 소수가 아님
        count += 1  # 소수가 아니면 count
    else:
        for div in range(2, num):
            if num % div == 0:  # 2부터 (자기자신-1)까지 한 번이라도 나누어 떨어지면 소수가 아님
                count += 1  # 소수가 아니면 count
                break
print(n - count) # 전체 경우에서 소수가 아닌 경우의 수를 빼면 소수인 경우의 수가 나옴