백준 (boj) 파이썬 - 1929 : 소수 구하기

문제 링크 : https://www.acmicpc.net/problem/1929

1929번: 소수 구하기

 

 

 

에라토스테네스의 체를 이용하면 된다.

https://infinitt.tistory.com/232

알고리즘 (1) - 수학 : 유클리드 호제법 , 에라토스테네스의 체 (나머지 연산, 최대 공약수, 최소공배수, 소수)

 원래 개념은 소수체크시, 범위**0.5 까지 이지만, int로 변환할때 반올림이 되어서그런가 오답이발생하였다. 그래서 0.8정도로 수정했지만 시간초과 없이 통과되었다.

 

 

 

파이썬 코드

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


r = N + 100

cheak = [False for _ in range(r)]

for i in range( 2, int(r**0.8) ) : # 2부터 ~ 범위(r)의 제곱근까지
    if cheak[i] == False : # 지워지지 않고, 가장 작은수라면
        for j in range( i*2 , r, i ): # i의 2배수 부터, 3배수, 4배수, .... 범위끝까지 지운다.(True로)
            cheak[j] = True

prime_number = [i for i,j in enumerate(cheak) if i>=2 and j==False]



for i in prime_number:
    if N >= i >= M:
        print(i)