[백준] 1929 파이썬(python) : 소수 구하기 - (에라토스테네스의 체)

1929번: 소수 구하기

 

 

 

시간초과가 났던 처음 코드)

m, n = map(int, input().split())
res = []
for i in range(m, n+1):
    error = 0
    for j in range(2, i):
        if i % j == 0:
            error += 1
    if error == 0:
        res.append(i)
for i in res:
    print(i)

 

 

에라토스테네스의 체를 적용해 시간을 줄인 코드)

m, n = map(int, input().split())
for i in range(m, n+1):
    if i == 1: #1
        continue
    for j in range(2, int(i**0.5)+1): #2
        if i % j == 0: #3
            break
    else:
        print(i) #4

 

 

#1 : 1은 소수가 아니므로 패스

#2 : 제곱근의 정수화한곳까지만 탐색

#3 : 여기서 약수가 발생하면 소수가 아니므로 반복문 탈출

 

 

에라토스테네스의 체를 이용하는 문제였다. #2를 이해하기 힘들었고 앞으로도 자주 나올 수 있을거라 생각한다.

 

 

https://hgk5722.tistory.com/139

[Algorithm] 에라토스테네스의 체, 소수 판정시 제곱근까지 확인하는 이유(python)

 

 

https://hgk5722.tistory.com/127

[백준] 1978 파이썬(python) : 소수 찾기