[Python] 백준 1978번 소수 찾기

문제

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

 

입력

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

 

출력

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

 

예제 입력	예제 출력
4 1 3 5 7	3

 

정답

import sys

if __name__ == '__main__':
    T = int(sys.stdin.readline().strip())
    nums = list(map(int, sys.stdin.readline().strip().split()))
    result = 0

    for i in nums:
        if i <= 1:
            continue

        for j in range(2, i + 1):
            if i == j:
                result += 1
            elif i % j == 0:
                break

    print(result)

 

Tip

소수란?

소수란 1 이상의 숫자가 1과 자기 자신으로만 나눠지는 수를 뜻한다.

그러므로 1은 1 이상의 숫자가 아니기 때문에 소수가 아니다.

 

break

import sys
from typing import List

if __name__ == '__main__':
    T: int = int(sys.stdin.readline().strip())
    nums: List[int] = list(map(int, sys.stdin.readline().strip().split()))
    cnt: int = 0
    res_cnt: int = 0

    for i in nums:
        cnt = 0

        if i <= 1:
            continue

        for j in range(2, i + 1):
            if i % j == 0:
                cnt += 1

        if cnt == 1:
            res_cnt += 1

    print(res_cnt)

다른 사람들의 코드를 보면 이런 형식의 코드가 몇몇 보인다. 하지만 이런 코드를 돌리게 된다면 i부터 자기 자신까지 다 돌려야 하므로 많은 for문이 돌아가게 된다. 목적을 달성했거나, 더 이상 돌릴 필요가 없는 경우 중간에 break를 사용하여 for문을 어떻게든 덜 돌리도록 하자.

for j in range(2, i + 1):
	if i == j:
		result += 1
	elif i % j == 0:
		break

 

횟수/실행시간	break 사용	break 미사용
1	80ms	84ms
2	72ms	72ms
3	68ms	80ms
4	68ms	72ms

백준 서버 상태에 따라 실행시간이 다르긴 하지만 참고용으로 알고 있으면 좋을 것 같다.

 

Multiple if vs if ~ elif

a = 1
b = 3

# a랑 b가 같은지 확인
if a == b:
	print('Same!')
    
# a가 더 큰지 확인
if a > b:
	print('a')
    
# b가 더 큰지 확인
if b > a:
	print('b')
    
# 총 3번 확인

a = 1
b = 3

# 위에 조건이 충족할 경우 밑에 있는 조건은 넘어감
# 최소 1번, 최대 3번

if a == b:
	print('Same!')
elif a > b:
	print('a')
elif b > a:
	print('b')

여러 개의 조건을 확인할 경우 우선 순위를 잘 정해서 if ~ elif를 쓰도록 하자.

※ 모든 조건을 확인해야 하는 경우는 다르다.