[정글 알고리즘]-[하]-백준1978 소수 찾기

📌 문제 요약

N개의 자연수 중 소수가 몇 개인지 출력하라.

소수: 1과 자기 자신만을 약수로 가지는 수 (단, 1은 소수 아님)

💡 소수 판별 원리

약수의 개수가 정확히 1개이면 소수.
1부터 n-1까지 반복하면 약수 중 1만 세이므로, 약수 카운트 == 1 이면 소수.

더 빠른 방법: 2부터 √n까지만 나눠보기 → 이 문제는 입력이 작아서 완전탐색도 OK

🐍 코드 분석

n = int(input())
a = list(map(int, input().split()))
count = 0

for num in a:
    divisors = 0
    for d in range(1, num):      # 1 ~ num-1 탐색
        if num % d == 0:
            divisors += 1
    if divisors == 1:            # 약수가 1 하나뿐 → 소수
        count += 1

print(count)

⚠️ 자주 하는 실수

실수	설명
1을 소수로 판단	1의 약수는 1뿐이지만 소수 정의에서 제외
range(1, num+1) 사용	자기 자신까지 세면 약수 개수 2개가 되어 소수 판별 실패