1978 소수찾기

TLDR

1 ~ n까지의 소수판별은 \(\sqrt n\) 까지만 검사하면 되는 문제였지. 왜냐고? #Notes를 확인하라.

---

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 \(\sqrt n\)? 모든 n은 어떤 두 정수 a, b의 곱으로 나타낼 수 있어야 한다. 그러면 a와 b의 조합을 살펴보면 대칭이라는 것을 알 수 있다. a 하나를 정하면 b는 \(\frac{n}{a}\) 가 되기 대문에 a = 1부터 차례로 계산해보다보면 어떤 값을 기준으로 a와 b가 대칭이 되는 것을 확인할 수 있다. 이때 a <= b를 만족하는 가장 큰 a 는 곧 \(\sqrt{n}\)이 된다는 것을 알 수 있다.