[백준] 1929번 소수 구하기(파이썬)

처음 만든 코드

import sys  
M, N = map(int, sys.stdin.readline().split())  

for i in range(M, N+1):  
    n_sosu = 0  
    if i == 1:  
        continue  
    for j in range(2, i):  
        if i == 2:  
            print(i)  
            break  

        elif i % j == 0:  
            n_sosu += 1  
            break  

    if n_sosu == 0:  
        print(i)

시간 초과 오류

문제

입력 받는 숫자의 범위가 큼
→ 많은 범위를 빠르게 거를 수 있게 수정해야 한다 .

수정 코드

import sys
M, N = map(int, sys.stdin.readline().split())

for i in range(M, N+1):
    n_sosu = 0
    if i == 1:
        continue

    for j in range(2, int(i**0.5)+1):
        if i == 2:
            print(i)
            break

        elif i % j == 0:
            n_sosu += 1
            break

    if n_sosu == 0:
        print(i)

변경점

j(나누는 범위)를 i**0.5함으로써 제곱근을 구하여 나눈다.

추가

n_sosu 없이 충분히 가능한 코드여서 빼는게 더 좋았을 것 같다.