반응형
문제
풀이
시간초과가 나와서 구글링해보니 에라토스테네스의 체를 이용해야 통과되는 문제이다.
에라토스테네스의 체
: 에라토스테네스의 체는 고대 그리스 수학자 에라토스테네스가 발견한 소수를 찾는 방법이다.
- 숫자의 제곱근 까지만 약수의 여부를 검증하는 방식이다.
1. 먼저 2를 제외한 2의 배수를 제거
2. 3을 제외한 3의 배수 제거
3. 5를 제외한 5의 배수 제거...
이런식으로 모든 구간에 대해 반복하면 소수만 남는다.
이것은
자신의 제곱근 까지만 약수의 여부를 검증하는 식으로 구현할 수 있다. (구글링을 통해 알게됨)
통과 된 풀이
def isPrime(num):
if num == 1:
return False
else:
for i in range(2, int(num ** 0.5) + 1):
if num % i == 0:
return False
return True
M, N = map(int, input().split())
for i in range(M, N + 1):
if isPrime(i):
print(i)
시간 초과 된 풀이
m, n = map(int, input().split())
for num in range(m, n+1):
if num > 1:
for i in range(2, num):
if num % i == 0:
break
else:
print(num)
반응형
'Algorithm > BaekJoon' 카테고리의 다른 글
[백준 9020] 골드바흐의 추측 python (0) | 2022.02.05 |
---|---|
[백준 4948] 베르트랑 공준 python (0) | 2022.02.04 |
[백준 11653] 소인수 분해 python (0) | 2022.02.04 |
[백준 1011] Fly me to the Alpha Centauri 파이썬 python (0) | 2022.02.02 |
[백준 2869] 달팽이는 올라가고 싶다 python (0) | 2022.02.02 |