[Python] BOJ 1929 - 소수 구하기(에라토스테네스의 체)

백준 1929번

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

1929번: 소수 구하기

가장 기본적인 소수 구하는 코드

* prime함수 : n을 매개변수로 넘겨받아 1부터 n-1까지 n%i = 0이면 a에 1을 더해줘서 최종적으로 a가 1이면 
  (모든 수는 1로 나누어지므로 모든 수의 a는 최소1이다) 소수 -> True 반환
* a,b를 입력받아 list1에 소수인 것들만 append해줬다.

* a와 b가 100만까지 들어오다보니 이 방법으로는 시간초과가 발생하였다.

 

* 따라서 새로운 방법인 '에라토스테네스의 체'를 사용해보았다.

출처 : https://ko.wikipedia.org/wiki/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98_%EC%B2%B4#/media/%ED%8C%8C%EC%9D%BC:Sieve_of_Eratosthenes_animation.gif

import math
def get_primes(a,b):
    # a부터 b사이의 소수를 구해야하지만 어쨋든 b칸의 리스트필요
    is_primes = [True] * b
    # b의 최대 약수가 sqrt(b)이하이므로 계산한 후, 소숫점이 있을 경우 올림으로 최대 반복횟수 계산
    max_length = math.ceil(math.sqrt(b))
    
    for i in range(2, max_length):
        # True일 경우, 소수
        if is_primes[i]:
            # i이후 i의 배수들 False처리 (이해 잘안가면 링크참고)
            for j in range(i+i, b, i):
                is_primes[j] = False

    # 리스트의 True로 남아 있는 인덱스(소수)를 추출
    return [i for i in range(a, b) if is_primes[i]]

a,b = map(int,input().split())
# a가 1일때 1부터 출력이 되므로 if문으로 나누어 주었다.(이 부분은 나중에 실력더 기르고 최적화시킬 것.)
if(a == 1):
    print(*get_primes(2,b+1), sep="\n")
else:
    print(*get_primes(a,b+1), sep="\n")

성공!