January 2, 2023

1978번: 소수 찾기

문제 요약

• 1,000 이하의 자연수 N개가 주어졌을 때 소수의 갯수를 출력
• 시간 제한 : 2초

풀이

import math

input()
arr = list(map(int, input().split()))

prime_list = [True] * 1001
prime_list[1] = False

for i in range(int(math.sqrt(1000))):
    if (not prime_list[i + 2]):
        continue
    j = 2

    while (i + 2) * j <= 1000:
        prime_list[(i + 2) * j] = False
        j = j + 1

cnt = 0

for num in arr:
    if (prime_list[num]):
        cnt += 1

print(cnt)

• 에라토스테네스의 체 이용

시간 복잡도

• 소수 리스트를 계산한 후 소수의 갯수를 판별하므로 input의 크기에 의존하지 않는다.
• O(1)