[백준 Python] - '1978 소수 찾기' 쉽게 풀기!

1. 문제 - 1978번

2. 접근법

주어진 수들 중에서 소수를 출력하는 문제다.

먼저 소수의 정의를 생각해보자. 소수란 '1과 자기 자신만을 약수로 가지는 수'이다.
이 점에 착안에 코드를 작성하면 아래와 같다.

 <정답 코드>

import sys
input = sys.stdin.readline

def prime_number(nums):
    prime_list = []

    for num in nums:
        divs = [i for i in range(1,num)] 
        cnt = 0
        for i in divs:
            if num%i == 0:
               cnt += 1
        if cnt == 1:
            prime_list.append(num)

    return len(prime_list)

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

print(prime_number(numbers))

먼저 표준 입력으로 주어진 수의 목록을 받는다.

해당 수들이 소수에 해당하는지 약수의 개수로 확인하는 함수를 만들어준다.

소수가 아니라해도, 모든 수는 1과 자기 자신을 반드시 약수로 가지며, 그외의 약수를 가지느냐 마느냐에 따라 소수의 여부가 결정된다.
즉, 소수의 약수는 반드시 1과 자기 자신 2개여야 하므로, 1은 소수가 아니며 약수가 3개 이상인 수는 소수가 될 수 없다.

따라서 입력받은 수들을 반복문 안에서 차례로 검사해줄 때, 1부터 자기자신 - 1까지의 임시 약수 집합을 만들고 이것들을 순서대로 나누어주며 약수에 해당하는지 검사해주면 된다.

주어진 수가 소수이려면 1부터 자기자신 - 1까지의 수 중에서 약수는 1 뿐이어야 하므로, cnt 가 1인 수만이 소수에 해당된다.
(1은 따로 코드를 작성해 걸러주는 경우가 많은데,
이렇게 임시 약수 집합을 만들어 검사하면, range(1,1)은 빈 리스트가 되어 cnt 가 0이 되므로 1은 소수가 아닌 수로 자동으로 걸러지게 된다.)