[Python] 백준 1978번_ 소수 찾기

문제

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

1978번: 소수 찾기

코드

length = int(input()) 
numList = list(map(int, input().split()))
cnt = 0 #소수가 아닌 수 카운팅

for num in numList: #리스트 안 숫자로 진행
  if num == 1: #1은 소수에 포함되지 않으므로 continue로 빠져나옴, 소수 아닌수 +1
    cnt+=1
    continue
  for i in range(2,num): #1이 아닌 숫자에 대해 2부터 나누며 소수인지 판별
    if num%i==0: #나머지=0 == 소수가 아님
      cnt +=1
      break #탈출

print(length-cnt) #전체 수 - 소수가 아닌 수 = 소수인 수 개수

풀이

• 소수의 개수를 직접적으로 구하는 것이 아닌 전체 수 - 소수가 아닌 수로 계산했다. 
• 약수를 구하는 문제에서 아이디어를 얻었다. num % i == 0일때, i는  num의 약수이다.
• 따라서 1, num을 제외한 수가 약수일 경우, 소수가 아니므로 카운팅해준다.
  • 하나라도 존재할 경우, 더 이상 계산할 필요가 없으므로 break로 다음 숫자로 넘어간다.