[백준 1978번] 소수 찾기

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

import sys

input = sys.stdin.readline

n = int(input())

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

# '1과 자기 자신 외의 약수를 가지지 않는 1보다 큰 자연수

count = 0

def checkPrime(N):

    prime_set = set(range(2,N+1))

    for i in range(2,N+1):
        if i in prime_set:
            prime_set -= set(range(2*i,N+1,i))

    if N in prime_set:
        return True
    else:
        return False


for num in numbers:
    if checkPrime(num):
        count += 1

print(count)

 

이번 문제는 주어진 N개의 숫자 중 소수의 개수를 구하는 문제이다.

 

처음에는 모든 수를 2부터 n-1까지 반복문으로 순회하면서 해당 숫자가 나눠지는지 확인하는 방법으로 풀이하려고 했는데, 시간복잡도를 최소한으로 줄이기 위해 '에라토스테네스의 체'를 활용하여 모든 숫자가 저장된 집합에서 2, 3 .. 의 배수부터 하나씩 지워주는 방식으로 소수를 구하고 그 집합에 속해있는지 여부를 통해 소수를 판별해주었다.