[백준/파이썬] 1929 : 소수 구하기

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

1929번: 소수 구하기

문제 요약 : M이상 N이하의 소수를 모두 출력하는 프로그램

 

황당하지만 가장 오랫동안(?) 못 푼 문제였음

그냥 아무 생각없이 소수를 구하는 프로그램을 짰고 언제나 시간초과가 떴다^^; 간단한 문제였어서 그냥 뭔가 줄이는 방법이 있겠지 하고 넘기고 넘기다가 그렇게 된듯.. 자기 과신의 결과다

결론적으로 말하면 질문 게시판에서 에라토스테네스의 체로 풀어야한다고 해서 겨우 풀었다.

 

 

 

에라토스테네의 체

고대 그리스의 수학자 에라토스테네스가 만들어 낸 소수를 찾는 방법

이 방법은 마치 체로 치듯이 수를 걸러낸다고 하여 '에라토스테네의 체'라고 부른다.

그림의 경우, 11의 제곱은 120보다 크므로 11보다 작은 수의 배수들만 지워도 충분하다.

즉, 120보다 작거나 같은 수 가운데 2, 3, 5, 7의 배수를 지우고 남는 수는 모두 소수이다.

=> 특정한 숫자의 제곱근까지만 약수의 여부를 검증하는 방식이다.

 

이 방식을 사용하면 시간복잡도가 O(N)에서 O(N^(1/2))로 줄어들게 된다.

 

 

 

풀이 1 )

리스트를 따로 만들지 않고 N부터 M까지 숫자를 돌면서 특정 숫자의 제곱근까지만 검증하는 방법

시간초과되지 않고 통과할 수 있다

def primeNumber(N,M):
    for now in range(N,M+1):
        if now > 1:
            sieve = True
            for i in range(2, int(now ** 0.5) + 1):
                if now%i == 0:
                    sieve = False
                    break
            if sieve:
                print(now)

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

풀이 2)

위 그림처럼 리스트를 만들어서 체에 거르듯 배수들 제거하는 방법

위의 방법보다 시간이 훨씬 절약된 것을 볼 수 있다

m, n = map(int, input().split())

def primeNumber(m, n):
  n += 1                            
  prime = [True] * n               
  for i in range(2, int(n**0.5)+1): 
    if prime[i]:                    
      for j in range(2*i, n, i):    
        prime[j] = False

  for i in range(m, n):
    if i>1 and prime[i] == True:
      print(i)

primeNumber(m, n)

 

📖 참고자료

위키백과-에라토스테네의 체