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

문제

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

입력

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

출력

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

코드

입력된 숫자 배열에서 가장 큰 숫자까지의 소수 여부를 한 번에 구하고, 이후 소수인지 여부가 저장되어있는 is_prime 배열에서 결과를 하나씩 출력했다.

def getPrime(n):
    is_prime = [True] * (n+1) # 1 ... n+1
    is_prime[0] = is_prime[1] = False
    
    for i in range(2, int(n**0.5) + 1): # i는 2부터 i의 제곱근까지 반복
        if not is_prime[i]:
            continue
        
        # i의 배수 지우기
        for j in range(i*i, n + 1, i):
            is_prime[j] = False
    
    return is_prime

# 입력
n = int(input())
nums = list(map(int, input().split()))

# 가장 큰 숫자까지 한 번에 소수 구하기
max_num = max(nums)
is_prime = getPrime(max_num)

# 소수 개수 카운트
cnt = 0
for num in nums:
    if is_prime[num]:
        cnt += 1

# 출력
print(cnt)