[5주_7일차] 백준-1978 소수(Python)

문제

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

입력

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

출력

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

 

 

 

<코드>

def is_prime(num):
    if num < 2:
        return False
    if num == 2:
        return True
    if num % 2 == 0:
        return False
    i = 3
    while i * i <= num:
        if num % i == 0:
            return False
        i += 2
    return True

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

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

print(count_primes)

 

 

<풀이과정>

-2보다 작으면 소수가 아님(0,1)

-2는 소수

-짝수는 소수가 아니므로 False 반환

-홀수인 경우에는 3부터 시작하여 제곱근까지 반복하며 나누어지는 수가 있는지 확인(소수 판별)

 

*제곱근까지만 반복하는 이유

-작은 약수의 짝인 큰 약수는 항상 작은 약수의 배수
-제곱근 이후의 약수들은 이미 제곱근 이하의 수에서 짝으로 확인되었기 때문