1978: 소수 찾기 - Python

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

문제

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

입력

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

출력

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

예제 입출력

풀이 1 (정답, 함수 정의)

n = int(input()) # 입력 받긴 했으나 이후 사용하진 않았음
numbers = map(int, input().split())

prime_cnt = 0 # 입력받은 정수들(numbers) 중 소수의 개수를 저장하는 변수
def prime_check(x): # 정수 x가 소수인지 검사하는 함수
	check_cnt = 0 # 정수 x의 약수의 개수를 저장하는 변수
	global prime_cnt # 'local variable referenced before assignment' 오류 해결을 위함
	for i in range(1, x+1):
		if x % i == 0:
			check_cnt += 1
	if check_cnt == 2: # 소수: 약수가 1과 자기 자신 뿐 => 약수의 개수(check_cnt)가 2여야 함.
		prime_cnt += 1

for number in numbers:
	prime_check(number)

print(prime_cnt)

정수 1을 예외처리 해줘야 하나, 등 여러 생각을 하다가
'약수가 1과 자기 자신 뿐'이라는 소수의 정의에 충실하게 풀어보고자 하였다.

문제점은

• 코드가 길다.
• 변수 n을 사용하지 않았다.
• 불필요하게 함수를 정의한 것 같다.
• 변수를 2개 사용했는데, 1개만 사용할 수는 없을까?

풀이 2 (정답)

n = int(input())
numbers = map(int, input().split())
prime_cnt = 0

for x in numbers:
	check_cnt = 0
	for i in range(1, x+1):
		if x % i == 0: check_cnt += 1
	if check_cnt == 2: prime_cnt += 1

print(prime_cnt)

풀이 1에서 함수를 정의하는 부분을 제거하였고, 코드를 보기 쉽게 고쳤다.
다른 코드들도 찾아봤는데 웬만한 블로그 글보다 내가 더 잘 푼 것 같다.

풀이 3 ('조무래기 코딩'님 블로그 참고)

n = int(input())
numbers = map(int, input().split())
count = 0

for x in numbers:
	for i in range(2, x+1): # 소수는 약수가 1과 자기 자신 -> 2부터 검사하면 자기 자신만 약수이면 된다.
		if x % i == 0:
			if x == i:
				count += 1
			break

print(count)

더 간단명료하게 푸신 분을 찾았다.
소수 구하는 문제가 많으니 익혀둬야겠다.

오늘의 교훈

• 소수인지 판별할 때, 검사 범위(나누는 수)를 2부터 자기 자신까지로 정해도 된다. (단, 이때는 약수의 개수가 1개여야 소수이다.)
• if 중첩, if-break 등 조건문을 영리하게 사용하면 보다 깔끔한 코드를 만들 수 있다.