소수 찾기

import sys


def main():
    input = sys.stdin.readline

    n = int(input())
    arr = list(map(int, input().split()))

    cnt_primes = 0
    for a in arr:
        if a == 1:
            continue
        for i in range(2, a):
            if a % i == 0:
                break
        else:
            cnt_primes += 1

    print(cnt_primes)

main()

소수

$1$보다 큰 양의 정수가 $1$과 자기 자신만으로 나누어 떨어지면, 그 수를 소수(prime number)라고 하고, 그렇지 않으면 합성수(composite number)라고 합니다. 따라서 모든 양의 정수는 다음과 같이 나뉩니다.

• 소수: $2$, $3$, $5$, $7$, $11$, $13$, $17$, $19$, $23$, $29$, ...
• 합성수: $4$, $6$, $8$, $9$, $10$, $12$, $14$, $15$, $16$, $18$, ...
• 소수도 합성수도 아닌 수: $1$

소수판별법

위 정의에 따라, $n$이 소수인지 판별하기 위해서는 $1$인지 확인하고, $2$부터 $n-1$까지의 수 중 아무것도 $n$을 나누어 떨어지게 하는 수가 있는지 확인하면 됩니다.

소수의 특성을 이용한 문제들이 아주 많기 때문에 개념을 잘 알아두면 좋습니다. 또한 위 방법보다 더 빠른 소수판별법들이 있는데, 사용할 필요가 있을 때 설명하도록 하겠습니다.