백준 python 1929 소수 구하기 : 시간초과 그리고 해결

1. 시간 초과 코드

첫 번째로 풀었을 때 시간 초과  코드. 시간 초과 될 것은 알았지만, 일단 써보자라고 생각하고 작성했다. 역시나 시간 초과.

import sys
input=sys.stdin.readline

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

for i in range(m, n+1):
    cnt=False #합성수 수
    for j in range(2, 1000001):
        if i % j ==0 and i !=j:
            cnt=True
    if cnt == False:
        print(i)

에라토스테네스의 체를 활용하여 경우의 수를 확 줄여서 문제를 푸는 것이었다.

결국 1~100 사이의 소수를 찾는다면, 루트 100 = 10 까지만 나눠서 확인해보면(2~10의 배수가 아닌 것이 확인되면)

소수라는 것을 확신할 수 있다는 뜻이다. 2의 배수, 3의 배수, 4의 배수 ... 차례로 모두 제거한다고 생각해보면, 10의 배수까지만 제거할 수 있다. 11*1~11*10까지는 이미 1~10의 배수에서 걸러졌고, 다음 11*11 부터는 해당 범위를 초과해서 볼 필요도 없다.

[에라토스테네스의 체 내용 참고]

https://namu.wiki/w/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98%20%EC%B2%B4

 

코드는 다음과 같다.

import sys
input=sys.stdin.readline
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): # 해당 수의 제곱근까지만 확인해주면 됨.
    	if i % j == 0: #나누어지면 멈추고,
        	break
    else:
    	print(i) #나누어지지 않으면 출력한다.