[백준/Python] 소수 구하기

 

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

 

---

소수 구하기 방법 3가지

https://seongonion.tistory.com/43

소수판별 알고리즘 - 파이썬 (Python)

 

1. 하나씩 보기

2. 제곱근

3. 에라토스테네스의 체

 

저는 2번과 3번을 구현해보겠습니다.

 

2. 제곱근

True: 소수

False: 소수가 아님

 

제곱근을 위해서는 math 라이브러리를 임포트 합니다.

from sys import stdin
from math import sqrt

m, n = map(int, stdin.readline().split())

for mn in range(m, n+1):
    r = True
    if mn == 1:
        continue
    else:
        for i in range(2, int(sqrt(mn))+1):
            if mn%i==0:
                r = False
                break

    if r==True:
        print(mn)

 

3. 에라토스테네스의 체

True: 소수

False: 소수가 아님

 

구현 방법:

- 0 ~ 최대값인 n까지 포함할 수 있는 arr 배열을 만든다(n+1)

- 0과 1은 False로 만든다

- arr 배열의 인덱스 = 값

- 인덱스의 배수를 False로 만든다(반복)

from sys import stdin

m, n = map(int, stdin.readline().split())

arr = [True] * (n + 1)
arr[0] = False
arr[1] = False

for i in range(2,n+1):
    if arr[i] == True:
        j = 2
        while i*j <= n:
            arr[i*j] = False
            j+=1


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

 

 

1번은 시간초과가 나고,

실제로 2번과 3번의 속도를 비교했을 때

2번 메모리/시간

3번 메모리/시간

 

굉장한 차이가 납니다.