728x90
https://www.acmicpc.net/problem/1929
소수 구하기 방법 3가지
https://seongonion.tistory.com/43
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번의 속도를 비교했을 때
굉장한 차이가 납니다.
'코딩테스트 문제' 카테고리의 다른 글
[백준/Python] 최대공약수와 최소공배수 (0) | 2024.09.11 |
---|---|
[백준/Python] 균형 잡힌 세상 (0) | 2024.09.09 |
[Python] 이진 탐색 (0) | 2024.09.08 |
[백준/Python] 동전 0 (0) | 2024.09.07 |
[프로그래머스/Python] 붕대 감기 (0) | 2024.08.07 |