백준 1929번 Python / Math

문제 링크

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

1929번: 소수 구하기

 

풀이

m,n = map(int, input().split())
state = 0

for i in range(m, n+1):
    state=0
    if i > 1:
        for j in range(2, i):
            if i % j == 0:
                state += 1
        if state == 0:
            print(i)

처음에는 위와 같은 풀이로 진행했습니다.

2부터 i-1 까지 모든 수를 체크해가며 출력하다보니 시간 초과가 발생했습니다.

 

import math

m,n = map(int, input().split())

for i in range(m, n+1):
    if i == 1:
        continue
    for j in range(2, int(math.sqrt(i)+1)):
        if i%j==0:
            break
    else:
        print(i)

어떻게 하면 좋을까 생각하다 모르겠어서 구글링을 통해 배웠습니다.

제곱근을 사용해 범위를 지정하면 해결이 된다고 해서 코드를 수정했습니다.

math.sqrt() 대신에 i**0.5 로 대체 가능