[백준/python] 1978 소수찾기:

 

import sys
arr=[]
n=int(sys.stdin.readline())
arr=list(map(int, sys.stdin.readline().split()))

cnt=0
for i in arr:
  if i==1: #1은 소수가 아님
    continue
  elif i==2: #2는 소수임
    cnt+=1
  else:
    for j in range(2,i):
      if i%j==0: #딱 나눠떨어지는 수가 하나라도 있으면 소수가 아님
        break
      if j==i-1: #for-loop를 다 도는동안 딱 나눠떨어지는 수가 없었다면(즉, 약수가 없다) 소수임
        cnt+=1
        
print(cnt) #소수 개수 출력

 

 

처음에 작성한 코드이다.

 

 

 

 

그런데 i의 모든 약수는 i/2보다 작다. 고로 2부터 i-1까지 확인할 필요가 없다는 뜻.

따라서 range(2,i)가 아니라 range(2,i//2+1)로 하면 시간복잡도를 반으로 줄일 수 있다.

i/2말고 제곱근을 사용하기도 하더라. range(2, int(n**0.5)+1)

핵심은 굳이 끝까지 다 돌 필요 없다는것!

 

참고 : https://veggie-garden.tistory.com/17 [Python] 소수 찾기 알고리즘