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

https://www.acmicpc.net/problem/1929

1929번: 소수 구하기

 

문제

 

21.03.05 접근법

 

에라토스테네스의 체 사용

 

 

21.03.05 코드

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

prime={1:False}

for i in range(2,n+1):
    prime[i]=True

for i in range(2,int(n**0.5)+1):
    for j in range(i+i,n+1,i):
        if prime[j]==True:
            prime[j]=False


for i in range(m,n+1):
    if prime[i]==True:
        print(i)

 

21.08.11 접근법

 

에라토스테네스의 체 사용

 

3월과 비교했을 때 메모리와 시간차이가 많이 났음.

3월 코드 (112236KB, 1716ms) : 딕셔너리 사용 / for문을 더 많이 돌림.

8월 코드 (36872KB, 448ms) : 리스트 사용 / 선택적 for문

 

 

21.08.11 코드

M,N=map(int,input().split())

prime=[True]*(N+1)
prime[1]=False

for i in range(2,int(N**0.5)+1):
    if prime[i]==True:
        for j in range(i+i,N+1,i):
            prime[j]=False

for i in range(N+1):
    if prime[i]==True and M<=i:
        print(i)