[Python][백준 BOJ Bronze II] 1978. 소수 찾기 : for else 문, 하나의 수에 대한 소수 판별

내 오답

import sys

n_num = sys.stdin.readline()	# 수의 개수
n = list(map(int, sys.stdin.readline().split()))	# n개의 수 입력

# n개의 수 중 소수 개수 (리스트 n에서 소수 개수)
prime_cnt = 0
for i in n:
    # 소수 판별. 소수는 1과 자기 자신(= i)으로만 나눠지는 수.
    if i < 2:
        continue
    else:   # i는 2 이상의 수
        for j in range(2, i):	# j는 2부터 (i - 1)까지의 수
            if i % j == 0:
                break
    prime_cnt += 1
print(prime_cnt)

if i % j == 0: break 가 수행되면 i는 1과 자기 자신 외의 숫자로도 나눠지기 때문에 소수가 아니므로 break을 사용해 for j in range(2, i) 루프를 종료시켰다. 

소수일 경우 break가 실행되지 않고 for j in range(2, i) 루프가 끝까지 실행되기 때문에 prime_cnt += 1 에 도달해 소수의 개수를 카운트할 수 있을거라 생각했다.

그치만 위 코드를 실행한 결과 2 이상의 모든 수가 카운트되었다.

문제점

for문이 break를 만나지 않고 끝까지 실행되었을 때 prime_cnt += 1 을 수행하려면 for-else문의 'else' 블록에 prime_cnt += 1 을 작성해야한다.

위의 코드처럼 작성하면 리스트의 모든 i에 대해 prime_cnt += 1 가 수행된다.

정답

import sys
n_num = sys.stdin.readline()    # 수의 개수
n = list(map(int, sys.stdin.readline().split()))    # n개의 수 입력

# n개의 수 중 소수 개수 (리스트 n에서 소수 개수)
prime_cnt = 0
for i in n:
    # 소수 판별. 소수는 1과 자기 자신으로만 나눠지는 수.
    if i < 2:
        continue
    else:   # i는 2 이상의 수
        for j in range(2, i):   # i가 1이 아닐 때 실행
            if i % j == 0:
                break
        else:    # 내부 루프가 break를 만나지 않고 완료되었을 때 실행
            prime_cnt += 1
print(prime_cnt)

⭐ for else 문 ⭐

for문에서의 else문은 break 등으로 중간에 빠져나오지 않고 전부 순회했을 때 실행되는 코드이다.

break문의 실행 여부에 따라 else문의 실행이 결정된다.

for문 내에서 break가 실행되면 for-else문의 else문이 실행되지 않고 for문 종료, break가 실행되지 않고 for문이 끝까지 실행되었다면 else문이 실행되고 for문 종료.

 

다른 풀이

하나의 수에 대해 소수인지 판별하는 함수를 작성하기

import math

# 소수 판별 함수
def is_prime_number(x):
    # 2부터 x-1까지의 모든 수 확인 => O(X). 비효율적!
    # 2부터 x의 제곱근까지의 모든 수 확인. => O(X^½). 시간복잡도 개선됨.
    for i in range(2, int(math.sqrt(x) + 1):
        # x가 i로 나누어 떨어지면
        if x % i == 0:
            return False
    # 모든 i에 대해 나누어 떨어지지 않으면 (반복문 끝까지 순회하면)
    return True
    
print(is_prime_nember(5))	# True
print(is_prime_nember(4))	# False

위의 방식으로 문제를 풀어보면 아래와 같다.

import sys
import math
n = int(sys.stdin.readline())   # 테스트케이스 개수
num = list(map(int, sys.stdin.readline().split()))

prime_cnt = 0
for i in num:
    if i < 2:
        continue
    for j in range(2, int(math.sqrt(i)) + 1):
        if i % j == 0:
            break
    else:
        prime_cnt += 1
print(prime_cnt)

---

+)  수의 범위가 주어졌을 때, 해당 범위 안에 존재하는 모든 소수 출력하려면?

에라토스테네스의 체를 사용하자.

 

2023.10.15 - [Algorithm & Data structure/문제 풀이] - [BOJ][Silver Ⅰ, Ⅱ] 6588. 골드바흐의 추측, 9020. 골드바흐의 추측 : 에라토스테네스의 체, 범위 내에 존재하는 모든 소수 찾기

[BOJ][Silver Ⅰ, Ⅱ] 6588. 골드바흐의 추측, 9020. 골드바흐의 추측 : 에라토스테네스의 체

 

---

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

1978번: 소수 찾기