[python] 1978. 소수 찾기

• 문제

---

---

 

• 잘못된 풀이

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

cnt = 0
for i in num:
    check = 0
    if i == 1:
        continue # 아래 코드를 실행하지 않고 건너뜀

    for j in range(2, i): # 소수는 2부터 자기자신-1으로는 나누어 떨어지지 않음
        if i % j != 0: # 나누어 떨어지지 않을 때, 1 -> 소수
            check = 1
        else: # 나누어 떨어지면 0 -> 소수 아님
            check = 0
            break
    if check == 1:
        cnt += 1
print(cnt)

 

소수는 1과 자기 자신으로만 나누어지는 수로, 약수가 2개인 수이다.

즉, 소수는 2부터 N-1까지의 수로 나누어지지 않는 수이다.

 

1은 소수가 아니기 때문에 continue를 통해 구분을 해주고,

나머지 2부터 N-1까지 나누어 떨어지지 않으면, check를 1로 하여 소수임을 나타내고

나누어 떨어지면, check를 0으로 하여 소수가 아님을 나타낸다.

 

이 때 나누어 떨어질 경우 for문에 break을 걸어 소수가 아닌 수가 소수로 변하는 경우를 막아준다.

 

나는 본문에 나와있는 예제를 통해 해당 알고리즘이 올바르다고 판단하고 제출하였지만

반례로 2가 소수임을 판별하지 못하여 문제 풀이에 실패하였다.

 

이는 check 기본 값은 0이고, 2는 for문에 들어가지 않기 때문에 check 값이 여전히 0임으로 소수로 판단하지 못하는 것이다.

 

 

• 올바른 풀이

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

cnt = 0
for i in num:
    check = 0
    if i == 1:
        continue # 아래 코드를 실행하지 않고 건너뜀

    for j in range(2, i): # 소수는 2~i-1로 나누어 떨어지지 않음
        if i % j == 0: # 나누어 떨어지면 1로 만들고 -> 소수 아님
            check = 1
            break
# i가 2인경우, 기존에 check=0이기 때문에 cnt+1이 됨
    if check == 0: # check 1이면 count+
        cnt += 1
print(cnt)

 

이는 올바른 풀이로, 위의 알고리즘처럼 여전히 1은 예외로 처리한다.

나머지 2부터 N-1까지의 수에 대하여 나누어 떨어지면 소수가 아닌것으로 판단하는데,

if문을 '== 0'(소수아님)이 아닌 '!= 0'(소수)조건으로 변경하였다.

 

따라서 소수가 아닌 경우에는 check를 1로 하고, break를 통해 소수가 아닌 경우에 for문을 바로 멈춘다.

해당 코드는 check를 0인 경우를 소수로 판단하게 하여, for문에 들어가지 않는 2도 소수로 올바르게 판단할 수 있도록 한다.

 

---

해당 문제를 통해 if, else문에 대한 효율적 작성(if만 쓰고 else는 생략하는)과 소수문제를 해결하는 알고리즘을 알게되었다.