[BOJ] 1978번 - 소수 찾기

---

문제설명

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

1978번: 소수 찾기

사고과정

• 다수의 소수를 찾는 알고리즘인 에라토스테네스의 체를 활용하면 된다.
• 주어지는 데이터의 최댓값이 1000이라고 했으므로 array 크기를 1001개로 초기화시켜준 후 한 번에 0부터 1000까지의 소수를 판별하고 난 후 주어진 nums를 하나씩 돌면서 해당 nums 인덱스에있는 array의 값이 True면 소수임을 의미한다.(0과 1은 소수가 아님을 잊지말자!)
• 또한 array 크기를 초기화시켜줄 때, 어차피 주어진 nums의 최댓값 + 1 의 길이만큼 초기화시켜줘도 무방하다.(이러면 이전보다 공간 복잡도는 줄어들 듯 하다!)

풀이

import math

n = int(input())
nums = list(map(int, input().split()))
max_num = max(nums)
array = [True] * (max_num + 1)
array[0] = False
array[1] = False

for i in range(2, int(math.sqrt(max_num))+1):
    if array[i]:
        j = 2
        while i * j <= max_num:
            array[i*j] = False
            j += 1
count = 0
for num in nums:
    if array[num]:
        count += 1
print(count)