[백준] 소수 구하기

출처:: www.acmicpc.net/problem/1929

분류:: 수학 

 

1. 문제 이해 및 해결과정

- n이 백만이므로 시간복잡도를 고려해야한다 - 에라토스테네스의 체를 이용하면 O(NloglogN)

 

2. 풀이방법

 1. 에라토스테네스의 체

#소수 구하기
#https://www.acmicpc.net/problem/1929
import sys
import math
sys.stdin = open("input.txt","r")
m,n=map(int,input().split())
sosu=[True]*(n+1)
sosu[1]=False
for i in range(2,int(math.sqrt(n))+1):
    if sosu[i]: #소수라면
        j = 2
        while i*j<=n:
            sosu[i*j]=False
            j+=1
for i in range(m,n+1):
    if sosu[i]:
        print(i)

 

3. 오답원인

 

4. 알게된 점