문제 💁🏻♂️
해결 과정
문제가 정말 짧고 간결하지만, 쉽지 않은 문제였다. 우선, 주어진 min 제한 범위로 인하여 당황했다. 10^12 이기 때문에 O(√min) 이내로 반드시 해결해야한다.
사고 과정 (1) ❗️
처음에는 에라토스테네스의 체 알고리즘을 적용했다. 알고리즘을 적용하여 2 ~ √max 까지의 모든 소수를 구한다. √max 까지의 소수를 구하는 이유는 제곱수를 제거하기 위함이다. 즉, (√max) ** 2 = max 를 사용하는 것이다. 그래서 나는 해당 로직을 통해 구한 소수들을 이용해서 min ≤ num ≤ max 인 num에 대해서 모든 prime 들에 대해서 탐색해보고자 했다.
num값보다 작거나 같으면서, 해당 num값의 제곱수로 나누어진다면 그 개수를 증가시켰다. 그 결과는 바로 시간 초과 였고, 시간 초과가 나지 않았더라도 오답이었을 것이다. 그 이유는 다음과 같다.
2 ~ (10^12 + 10^6) 까지의 소수의 개수는 78_498개이고, min ~ max 사이의 숫자는 최대 10^6이기 때문에 시간 초과가 난 것이다. 또한, 제곱수만 생각하고, 제곱수의 배수는 생각하지 않았기 때문에 시간 초과가 나지 않았더라도 오답이다.
사고 과정 (2) ‼️
곰곰히 생각해보았지만, 별다른 아이디어가 떠오르지 않아서 여러 블로그를 찾아보았다. 너무 에라토스테네스의 체 알고리즘에 꽂혀서 시야가 좁아졌던 것 같다. 이 문제를 풀기 위해서는 min ≤ num ≤ min + 1_000_000 을 알아차리는 것이 핵심이었다. 결국 탐색 범위는 10^6 이라는 점이다. 이 탐색 범위 내에서 에라토스테네스의 체 알고리즘이 간접적으로 반영된다. 풀이 과정은 다음과 같다.
min = 30, max = 100 이라고 하자.
- 첫 제곱수인 (2 2)부터 시작하자. min 값에 대해서 min // (2 2) 값을 구한다.
- 정확이 나누어 떨어지지 않는다면
몫 * (2 * 2)값이 min값보다 작아지므로, 작아지는 것을 방지하기 위해서 나누어 떨어지지 않는다면 몫에 1을 더해준다. ex) 30 // 4 = 7 -> 8 - 그 몫(8)과 제곱수(2 * 2)에 대해서 max까지 가능한 모든 제곱 수들을 방문 처리 해주고, cnt 값을 줄인다.
- 이와 같은 과정을 (3 3), (4 4) ,,, (i * i) <= max 까지 반복한다.
- 반복하는 과정에서 이미 방문 처리된(중복된) 값은 신경쓰지 않는 로직을 넣어준다.
- cnt 값을 출력한다.
이를 구현하여 제출한 결과 정답 판정을 받았다! 골드1 문제는 역시 쉽지 않았다.
코드
오답 코드 (시간 초과)
from sys import stdin
from math import isqrt
input = stdin.readline
LEN = isqrt(10 ** 12 + 10 ** 6)
sieve = [False, False] + [True] * (LEN - 1)
for i in range(2, isqrt(LEN) + 1):
if sieve[i]:
for j in range(i * i, LEN + 1, i):
sieve[j] = False # 합성수 제거
primes = [i for i in range(2, LEN + 1) if sieve[i]]
mn, mx = map(int, input().split())
cnt = 0
for num in range(mn, mx + 1):
for prime in primes:
if (prime ** 2) <= num and num % (prime ** 2) == 0:
cnt += 1
break
ans = mx - mn + 1 - cnt
print(ans)정답 코드
from sys import stdin
input = stdin.readline
mn, mx = map(int, input().split())
LEN = 10 ** 6
sieve = [True for _ in range(LEN + 1)]
cnt = mx - mn + 1
for i in range(2, mx + 1):
if i ** 2 > mx:
break
qt = mn // (i ** 2) if mn % (i ** 2) == 0 else (mn // (i ** 2)) + 1
while qt * (i ** 2) <= mx:
if sieve[qt * (i ** 2) - mn]:
sieve[qt * (i ** 2) - mn] = False # 제곱 ㅇㅇ 수
cnt -= 1
qt += 1
print(cnt)
Reference
