[백준] 1929번: 소수 구하기 python

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

1929번: 소수 구하기

 

처음 작성한 코드:

a,b= map(int, input().split())
for i in range(a,b+1):
  cnt = 0
  if i > 1:
    for j in range(2,i):
      if i % j == 0:
        cnt += 1
    if cnt == 0:
      print(i)

답은 나오지만 시간 초과 발생 

 

소수는 자신과 1밖에 약수가 없는 수이다.

그럼 모든 수를 돌면서 나누어 떨어지는 수가 있는지 없는지 보면 되는데

모든 수를 봐야할 필요는 없었다.

 

약수는 대칭으로 이루어져있기 때문에

해당 수의 제곱근까지만 나눠보면 된다.

 

예를 들면, 12의 약수는 1 2 3 4 6 12 / 1*12 , 2*6, 3*4 로 대칭

81의 약수는 1 9 81 / 1*81 , 9*9 로 대칭

 

즉, 제곱근 보다 같거나 작은 수까지만 나눠보고 나누어 떨어지는게 있냐 없냐 확인하면 된다

 

정답 코드:

a,b= map(int, input().split())
for i in range(a,b+1):
  if i == 1:
    continue
  for j in range(2,int(i**0.5)+1):
    if i % j == 0:
      break
  else:
    print(i)