1978 소수찾기
TLDR
1 ~ n까지의 소수판별은
Snippet
"""
boj.kr/1978
"""
from collections.abc import Sequence
from math import sqrt, ceil
def preprocess(MAXN: int) -> list[bool]:
"""에라토스테네스의 체, 소수일 경우 True"""
isprime = [True] * (MAXN + 1)
isprime[0] = False
isprime[1] = False
for i in range(2, int(sqrt(MAXN + 1))):
if not isprime[i]:
continue
for j in range(2, ceil((MAXN + 1) / i)):
isprime[i * j] = False
return isprime
PRIMES = [i for i, e in enumerate(preprocess(1000)) if e] # [2, 3, 5, 7, ... , 997]
def main(nums: Sequence[int]) -> int:
return sum([1 for x in nums if x in PRIMES])
if __name__ == "__main__":
# print([i for i, e in enumerate(preprocess(1000)) if e])
n = int(input())
print(main(map(int, input().split())))
Sample Input & Expected Output
Input
4
1 3 5 7
Expected Output
3
Notes
WHY