백준_python 1929번 소수 구하기(시간 초과, 에라토스테네스의 체)

<문제 링크>

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

1929번: 소수 구하기

 

 

 

<정답 코드>

sol1)  m부터 n 사이의 숫자들이 약수인지 여부를 특정 숫자의 제곱근까지만 확인하여 판별

 

m, n = map(int, input().split())
 
for i in range(m, n+1):
    if i == 1:
        continue
    # i의 제곱근까지만 검사
    for j in range(2, int(i ** 0.5) + 1):
        if i % j == 0:
            break
    else:
        print(i)

 

 

sol2)  에라토스테네스의 체 알고리즘으로 검색 범위 축소하여 소수 판별

 

def find_prime(m, n):
    if m <= 2:
        print(2)
 
    # 홀수 소수 찾기 위한 초기화
    # 첫번째 False는 1이 소수가 아님을 의미, 처음엔 모든 홀수를 소수 후보로 간주(True)
    primes = [False] + [True] * ((n - 1) // 2)
 
    # 에라토스테네스의 체 알고리즘
    for k in range(1, int((n ** 0.5) / 2) + 1):
        if primes[k]:
            # k가 소수인 경우 k의 배수들을 False 로 설정
            primes[2 * k * (k+1) :: k * 2 + 1] = [False] * (((n + 1) // 2 - k * k * 2) // (k * 2 + 1))
 
    # m 이상 n 이하 소수 출력
    for i, is_prime in enumerate(primes[m//2:], start = m//2):
        if is_prime:
            prime_num = 2*i + 1
            if prime_num >= m:
                print(prime_num)
 
m, n = map(int, input().split())
find_prime(m, n)

 

 

 

---

 

sol 1 vs sol 2

sol1보다 sol2의 코드가 더 길고 복잡하지만,

에라토스테네스의 체 알고리즘을 활용한 sol2의 검색 범위가 훨씬 좁기 때문에 속도가 빠르다.

=> 채점 결과 약 50배의 속도 차이 발생