[백준] 1978번 소수 찾기 파이썬

Siver 4에 해당하는 문제이다.

주어진 수 N개 중에서 소수가 몇 개인지 찾고, 소수의 개수를 출력하는 문제이다.

 

1978번 소수 찾기 풀이

 

파이썬 연산자 중에서 %는 나머지를 찾아준다. ( /는 나눈 몫의 실수형, //는 나눈 몫의 정수형 )

소수에는 1이 포함되지 않는다.

1 이외의 자연수 중에서 1과 자기자신으로만 나누어 떨어지는 수를 소수(prime number)라고 말한다.

 

[시도1] pypy3 틀렸습니다

import sys

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

for i in numbers:
  #1은 소수가 될 수 없으므로 1이 아닌 모든 수
  if i != 1:
    for j in range(2,i):
      if i % j == 0:
        isprime = False
      else:
        isprime = True
        break
    if isprime == True:
      cnt += 1
    else:
      continue        

  #1은 소수가 될 수 없으므로 1은 카운트를 하지 않음
  else:
    continue

print(cnt)

입력받은 숫자들 중에서 1이외의 나머지 자연수들을 2부터 자기자신보다 하나 작은 수까지로 나누었을 때 나누어떨어져서 나머지가 0이면 소수가 아니고, 나머지가 0이 아니면 소수일 수도 있다는 논리로 반복문을 만들었다. 결과적으로 소수이면 cnt에 1을 더해서 마지막 소수의 개수를 출력할 수 있도록 했다.

예제 입력 값에 오류가 없어 제출했으나 틀렸고, 반례로 2만 입력했을 때, 소수이므로 1이 출력되어야 하는데 0이 출력된다는 것을 알게 되었다.

 

[시도2] pypy3 틀렸습니다

import sys

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

for i in numbers:
  
  if i > 2:
    for j in range(2,i):
      if i % j == 0:
        isprime = False
      else:
        isprime = True
        break
    if isprime == True:
      cnt += 1
    else:
      continue        
  
  #2는 위의 for문에서 작동 불가능하므로 여기서 소수로 카운트
  elif i == 2:
    cnt += 1

  #1은 소수가 될 수 없으므로 1은 카운트를 하지 않음
  else:
    continue

print(cnt)

[시도1]의 반례였던 2에 대한 경우를 추가해 주었다. 

그러나 틀렸다고 하였고 4만 입력했을 때, 소수가 아니므로 0이 출력되어야 하는데 1이 출력된다는 것을 알게 되었다.

 

[시도3] pypy3 맞았습니다!!

import sys

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

for i in numbers:
  
  if i > 2:
    for j in range(2,i):
      if i % j == 0:
        isprime = False
        break
      else:
        isprime = True
        continue
    if isprime == True:
      cnt += 1
    else:
      continue        
  
  #2는 위의 for문에서 작동 불가능하므로 여기서 소수로 카운트
  elif i == 2:
    cnt += 1

  #1은 소수가 될 수 없으므로 1은 카운트를 하지 않음
  else:
    continue

print(cnt)

[시도2] 코드에 4만 확인할 때에 왜 오류가 나는지에 대해 고민해보니 isprime이 False이면 다시 반복문을 돌면서 나눗셈을 확인하는데 True인 경우에 break를 시킨다는 것을 확인할 수 있었다. 반대로 isprime이 False이면 소수가 아니므로 바로 반복문을 나가도 되고, isprime이 Ture이면 소수일 수도 있으니 다음 나눗셈 확인을 해보아야하는 것이었다. 이 부분을 수정해 주었더니 정답으로 인정받을 수 있었다.

 

 

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

1978번: 소수 찾기