백준 1929번 파이썬

1. 문제

2. 설명

시간복잡도를 줄여주기 위해, i의 제곱근까지만 검사해주는 방식을 사용했다. 

i를 2부터 i의 제곱근까지의 수로 나누어주며, 나누어진다면 cnt를 1 증가시킨 후 break한다.

만약 끝까지 어떤 수로도 나눠지지 않았다면(cnt=0) i값을 출력해준다.

3. 코드

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

정말 오랜만에 정답 검색안하고 내가 오롯이 푼 코드로 '맞았습니다!' 를 받았다!! ㅠㅠ

까다로운 백준 너란녀석..