백준 1929번 문제(소수 구하기) 파이썬(Python) 풀이 [로밍맨]

문제 링크

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

1929번: 소수 구하기

 

정답 코드는 아래와 같습니다.

import sys
 
def solve():
  M, N = map(int, sys.stdin.readline().rstrip().split())
  primes = [True] * (N+1)
  primes[1] = False
  for i in range(2, N+1):
    if primes[i]:
      for j in range(i*2, N+1, i):
        primes[j] = False
  for i in range(M, N+1):
    if primes[i]:
      print(i)
 
solve()

 

에라토스테네스 라는 기원전 고대 그리스 수학자가 생각해 낸 소수를 구하는 방식을 적용하여 풀 수 있는 문제입니다.

단순 복잡도를 계산해보면, for 문이 2개 중첩되므로 O(n^2) 이지만,

사실상 line 8 에서 대부분의 경우(소수가 아닌 수인 경우) 그 다음 단계로 넘어가지 않기 때문에

실제 복잡도는 O(nk) (n 이하의 k는 소수의 갯수) 이며, k 는 n 이 커짐에 따라 증가하는 속도가 매우 작기 때문에 시간 안에 계산이 가능합니다.

제가 영상에서 이야기하지는 않았지만 이 방식은 사실 DP 입니다.

(DP라는 용어가 생긴 것은 1900년대 중반이지만, 사실 DP는 기원전부터 사용되던 방식인 겁니다)

 

필요한 분들이 있을 수 있으니, 영상에서 사용했던 정의를 이용하여 구현한 코드와

이를 조금 더 최적화 하여 sqrt(square root) 까지만 계산하는 코드를 첨부합니다.

 

728x90

 

정의를 이용한 방식 O(n^2)

import sys
 
def isPrime(number):
  if number == 1:
    return False
  for i in range(2, number):
    if number % i == 0:
      return False
  return True
 
def solve():
  M, N = map(int, sys.stdin.readline().rstrip().split())
  for i in range(M, N+1):
    if isPrime(i):
      print(i)
 
solve()

 

sqrt 최적화 방식 O(n*sqrt(n)) = O(n^(3/2))

import sys
import math
 
def isPrime(number):
  if number == 1:
    return False
  for i in range(2, int(math.sqrt(number)) + 1):
    if number % i == 0:
      return False
  return True
 
def solve():
  M, N = map(int, sys.stdin.readline().rstrip().split())
  for i in range(M, N+1):
    if isPrime(i):
      print(i)
 
solve()
 

 

풀이는 아래 영상을 참고 바랍니다.

https://www.youtube.com/watch?v=OFLATbdiZhY 

 

 

저작권 라이선스: CC BY (출처만 표시하면 자유롭게 이용 가능)