[백준 1978번] 소수 찾기

문제 보기

이 문제는 수학 문제이다.

알고리즘 분류는 에라토스테네스의 체도 포함되어 있지만, 굳이 그럴 필요는 없는 것 같다.

문제에서 요구하는 바는 주어진 숫자들 중 소수가 몇 개인지 찾는 것이다.

딱히 어려운 구현은 없기 때문에, 나는 소수를 판별하기 위해 다음의 조건을 생각하였다.

소수의 약수는 1과 n밖에 없다.

이 조건을 확인하는 함수는 8~16번째 줄에 작성되어 있다.

 

문제를 푼 로직은 다음과 같다.

1. 자연수를 입력받는다. (4~5번째 줄)
2. 주어진 수에 대해서 소수의 개수를 세고, 이를 출력한다. (19~23번째 줄)

 

import sys
from math import sqrt

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


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


answer = 0
for i in numbers:
	if is_prime(i):
		answer += 1
print(answer)