[백준] 1978번 소수 찾기 - 파이썬(Python)

문제 (링크)

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

1978번: 소수 찾기

 

나의 풀이

n = int(input())
data = list(map(int, input().split()))
count = 0

for x in data:
  for i in range(2, x+1):
    if x % i == 0:
      if x == i:
        count += 1
      
      break

print(count)

 

백준에서 틀린 문제를 살펴보다가 발견한 문제다. 

 

왜 그랬는지는 모르겠는데 꽤 많이 틀려놨었고, 발견하자마자 풀어봤는데 바로 풀렸다.

 

알고리즘 문제 중 소수와 관련된 문제는 그리디 방식으로 모든 경우의 수를 다 찾아보는게 정수이다.

 

주어진 수를 2부터 (1은 소수가 아니므로) 해당 숫자 X까지 for문으로 돌면서 X와 나누어 떨어지는지 검사한다.

 

그러다 X에 도달하지 못하고 중간에 나누어떨어지는 수를 만나게되면 해당 수는 소수가 아니므로 나머지 반복문을 볼 필요 없이 break 해준다.

 

숫자가 X에 도달 후 나누어떨어지게 된다면, 그 수는 소수라고 볼 수 있으므로 미리 정의해놨던 count에 +1을 해줘 숫자를 세준다.