[백준] #1978 소수찾기(python)

📌문제

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

입력

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

출력

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

💻코드

import sys
import math

num = int(sys.stdin.readline().strip())
numList = list(map(int, sys.stdin.readline().split()))

def isPrime(x):
    if x < 2:
        return False
    for y in range(2, int(math.sqrt(x)) + 1):
        if x % y == 0:
            return False
    return True


answer = len(list(filter(isPrime, numList)))

print(answer)

💡Idea

소수는 1보다 큰 자연수 중 1과 자기 자신만을 약수로 가지는 수입니다. 따라서 2부터 x-1까지의 수로 x를 모두 나누어보면 소수인지 아닌지를 확인할 수 있습니다.
하지만 이 방법은 비효율적이기 때문에, 2부터 x에 루트를 씌운 값까지의 수로 x를 나누어 소수인지를 판별하기로 했습니다.

📝코드 설명

변수

• num : 입력될 숫자들의 개수
• numList : 입력된 숫자들을 담고 있는 리스트
• answer : numList에 존재하는 소수의 개수

함수

• isPrime(x) : x가 소수면 True, 아니면 False를 return하는 함수

isPrime이라는 함수를 만든 뒤, numList의 값들을 filter를 통해 소수인 것들만 골라 그 개수를 출력할 수 있도록 했습니다.

isPrime 함수의 내용은 소수 찾기 알고리즘을 확인하면 더 이해하기 쉽습니다!!