[백준] 1929번 :소수 구하기 - Python 파이썬

[백준] 1929번 :소수 구하기 - Python 파이썬

 

알고리즘 분류:

• 수학
• 정수론
• 소수 판정
• 에라토스테네스의 체

 

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

1929번: 소수 구하기

 

---

문제

M이상 N이하의 소수를 모두 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다.

출력

한 줄에 하나씩, 증가하는 순서대로 소수를 출력한다.

 

 

---

제출한 답

m, n = map(int, input().split())
if m == 1: m = 2

for num in range(m,n+1):
  for i in range(2,int(num**0.5)+1):
    if num % i == 0:
      break
  else:
    print(num)

해당 범위 내의 수를 하나씩 소수인지 확인하고 프린트하는 방식.

간결하고 사실 백준에서도 맞았다고 풀이된다.

해당 수들에서 제곱근까지만 조사하므로 시간이 단축되었기 때문이다.

 

하지만 시간이 6340ms라고 뜬걸보고

이건 쫌;;; 하고 다른 답을 생각해보았다.

 

m, n = map(int, input().split())
prime = [False,False] + [True]* (n-1)#0,1은 False처리

for i in range(2,int(n**0.5)+1):
  if prime[i] == True: # i가 소수인 경우 
    for k in range(2*i, n+1, i): #i이후 i의 배수들(k)을 False 판정
      prime[k] = False;

for i in range(m,n+1):
  if prime[i]:
    print(i)

해당 코드는 에라토스테네스의 체를 이용했다.

별거 아니고 0-n까지 불린으로 이뤄진 배열을 생성한 뒤

2,4,6.../3,(6x),9... 식으로

not 소수인 인덱스의 배열값을 False로 만들어주는 것이다.

 

귀찮고 코드가 길어지지만, 소수인지 조사해야 할 숫자가 많아질수록 효과적이다.

 

실행시간은 448ms로 확실히 빨라졌다.

대신 메모리가 많아졌다. (1부터의 배열을 만들어 저장해서)