[백준] 1978번 소수 찾기 해설 및 풀이 (Python)

백준 1978번 소수 찾기

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

 

---

 

문제

주어진 수 N개 중에서 소수가 몇 개인지 찾아서 출력하는 프로그램을 작성하시오.

입력

첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다.

출력

주어진 수들 중 소수의 개수를 출력한다.

 

 

문제 유형

수학

정수론

소수 판정

 

풀이 방법 도출

 

이 문제는 주어진 N개의 숫자 리스트 중에서 소수의 개수가 몇 개인지 출력하는 문제입니다.

소수란 1과 자기 자신을 제외하고는 약수가 없는 자연수입니다.

따라서 소수를 판별하고, 소수일 때 count 변수를 +1씩 증가시켜서 최종적으로 count를 출력하면 됩니다.

 

1. 소수를 판별하는 함수 is_prime을 선언합니다. 소수는 n이 2보다 작은 경우 소수가 아니기 때문에 False를 반환합니다. 2부터 √n 까지 반복하며, n이 그 수로 나누어 떨어지는지 확인합니다. 하나라도 나누어떨어지면 소수가 아니므로 False 반환하고, 모두 나누어떨어지지 않으면 소수이기 때문에 True 반환합니다.
2. 첫 줄에 수의 개수 N을 입력 받습니다. 두 번째 줄에 N개의 숫자 리스트를 입력 받습니다.
3. 소수라면 count를 1 증가시킵니다.
4. 소수의 개수(count) 출력합니다.

---

 

핵심 코드 삽입 및 설명

 

import sys
import math

def is_prime(n):
    if n < 2:
        return False
    for i in range(2, int(math.sqrt(n)) + 1):
        if n % i == 0:
            return False
    return True

input = sys.stdin.readline
n = int(input())
numbers = list(map(int, input().split()))

count = 0
for number in numbers:
    if is_prime(number):
        count += 1

print(count)