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

문제

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

---

문제 설명

1.   M이상 N이하의 소수를 증가하는 순으로 모두 출력해야 한다.

 

---

풀이

소수를 판별하는 방식에는 여러가지가 존재한다.

 

1. 범위 내의 모든 수를 소수인지 확인한다.

import sys
input = sys.stdin.readline

def find_prime(num):
   for i in range(2,num):
      if num % i == 0:
         return False
   return num


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

for num in range(M, N+1):
   prime = find_prime(num)
   if prime:
      print(prime)

모든 수를 검사하면 M,N까지 최대 $O(N)$만큼 소요되고 find_prime() 함수를 호출할 때 $O(N)$만큼 소요되므로

총 $O(N^2)$의 시간복잡도를 가지게 된다.

문제에서 최악일 경우 $N = 10^6$이므로 $O(10^12)$의 시간복잡도를 가진다.

문제에서 요구하는 제한 시간은 1초, 즉 $O(10^8)$안에 해결해야 하므로 해당 방식은 적합하지 않다.

 

2. 범위를 $\sqrt{n}$으로 줄이고 소수인지 확인한다. 

import sys
import math
input = sys.stdin.readline

def find_prime(num):
   for i in range(2,int(math.sqrt(num)) + 1):
      if num % i == 0:
         return False
   return num


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

for num in range(M, N+1):
   prime = find_prime(num)
   if prime:
      print(prime)

만약 n  = 100이라고 가정하자.

소수는 약수가 1과 자신뿐이어야 한다. n을 나눌 수 있는 최대 숫자는 $\sqrt{100} = 10$이다. 이보다 더 큰 숫자로는 n을 나눌 수 없다. 따라서 범위를 루트로 줄이게 되면 그 이상의 숫자는 검사할 필요가 없어진다.

해당 방식으로 변경했을 때 시간복잡도는 최초 검사할 때$O(N)$, 소수를 판별할 때 $O(\sqrt{N})$

즉 $O(N*\sqrt{N})$, $O(10^9)$의 시간복잡도를 가지게 된다.

따라서 해당 방법 또한 적합하지 않다.

 

3. 에라토스테네스의 채를 통해 소수를 판별한다.

N까지의 모든 수를 나열한 후 나열한 수 하나하나 배수들을 전부 제거하는 방식으로 소수를 찾는다.

 

 

1. N이 10이라고 가정하자. = (2,3,4,5,6,7,8,9,10)
2. i = 2일 때 2의 배수 제거 : (2,3,5,7,9)만 남게된다.
3. i = 3일 때 3의 배수 제거 :  (2,3,5,7)
4. i = 4....10 반복
5. 결과 : (2, 3, 5 ,7)

이런식으로 N까지 모든 수의 배수를 제거하면 소수만 남게된다.

 

따라서 시간복잡도는 N번만큼 반복 = O(N), i의 배수를 지울 때 $O(log_{log_N})$이다.
총 시간복잡도는 $O(N * log_{log_N}) = O(10^6 * 32)$의 시간복잡도가 소요된다. 

따라서 해당 문제를 풀이할 때 적합하다.

 

에라토스테네스는 아주 큰 범위의 소수를 구할 때 적합한 알고리즘이다.

---

코드

import sys
input = sys.stdin.readline

def find_prime(m,n):
    primes = [i for i in range(n+1)]
    primes[1] = 0
    for i in range(2,n+1):
      for j in range(i*2, n+1, i):
         if primes[j]:
            primes[j] = 0
    
    for prime in primes[m:n+1]:
       if prime:
          print(prime)

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

find_prime(M,N)

---

시간복잡도

• $O(N * log_{log_N}) = O(10^6 * 32)$