[백준] 1929번 : 소수 구하기 (Python)

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

 

M이상 N이하의 소수를 모두 출력하는 문제.

 

import sys

input = sys.stdin.readline

# 소수 구하기
def prime(N):
    
    a = [False,False] + [True]*(N-1)
    primes=[]

    for i in range(2,N+1):
        
      if a[i]: # 소수이면
        primes.append(i)
        
        for j in range(2*i, N+1, i): # i의 합성수를 지움
            a[j] = False
    
    return primes

N, M = map(int, input().split()) # N, M
primes = prime(M) # 소수를 구함

for pri in primes:
    
    if(pri >= N): # N 이상이여야 하므로
        print(pri)

 

 

[문제풀이]

---

 

소수는 1과 자기 자신을 제외한 다른 수로 나누어 떨어지지 않는 수다.

일반적으로 반복문을 사용해서 검사를 하게 되는데, 이 방식으로는 시간 초과가 나기 때문에 시간 안에 풀 수 없다.

 

그래서 에라토스테네스의 체를 사용해서 문제를 풀어야 한다.

에라토스테네스의 체란 범위 안의 모든 합성수를 지워서 소수를 구하는 방식이다.

 

 

 

 

2부터 n까지 n의 배수를 모두 제거하면 범위 안의 소수를 모두 구할 수 있으며,

O(n log(logn))의 시간 복잡도로 시간 안에 문제를 해결할 수 있다!

 

 

참고 : https://wikidocs.net/21638