[백준] - 1929 소수 구하기 (Python)

문제 링크

풀이과정

일단 먼저 아래와 같이 for문을 돌면서 자기 자신과 1 외에 나누어 떨어지는 게 있으면 check 표시를 해 check가 0인 애들만 출력하는 식으로 코드를 작성했다.

import sys
m,n=map(int, sys.stdin.readline().strip().split())
for i in range(m, n):
    check=0
    for j in range(i-1,1,-1):
        if i%j==0:
            check=1
            break
    if check==0:
        print(i)

그리고 결과는 (역시나) 시간초과,,, ㅠㅠ
그래서 에라토스테네스의 체를 이용해 문제를 풀어보았다. 범위 잘못 설정해서 틀렸습니다 떠가지고 매우 당황함.. 문제 요구사항 꼼꼼히 살펴보자!!

코드

import sys
m,n=map(int, sys.stdin.readline().strip().split())
l1=[True]*(n+1)
l1[0]=l1[1]=False
for i in range(2, n+1):
    if l1[i]==True:
        for j in range(i+i, n+1, i):
            l1[j]=False
for k in range(m, n+1):
    if l1[k]==True:
        print(k)

참고 에라토스테네스의 체