๋ฌธ์
https://www.acmicpc.net/problem/1456
๋ฐฑ์ค ๋ฌธ์ ์ง - 0x12๊ฐ - ์ํ
์๊ณ ๋ฆฌ์ฆ: ์ํ, ์ ์๋ก
ํ์ด
์ด๋ค ์๊ฐ ์์์ N์ ๊ณฑ(N ≥ 2) ๊ผด์ผ ๋, ๊ทธ ์๋ฅผ ๊ฑฐ์ ์์๋ผ๊ณ ํ๋ค.
๋ ์ ์ A์ B๊ฐ ์ฃผ์ด์ง๋ฉด, A๋ณด๋ค ํฌ๊ฑฐ๋ ๊ฐ๊ณ , B๋ณด๋ค ์๊ฑฐ๋ ๊ฐ์ ๊ฑฐ์ ์์๊ฐ ๋ช ๊ฐ์ธ์ง ์ถ๋ ฅํ๋ค.
์๋ผํ ์คํ ๋ค์ค์ ์ฒด ๋ฌธ์ ๋ค.
๋จ, ๋ฆฌ์คํธ์ ํฌ๊ธฐ๋ฅผ B์ ๋ง์ถฐ ์ค์ ํ๋ฉด ๋ฉ๋ชจ๋ฆฌ ์ด๊ณผ๊ฐ ๋๋ค.
๋ฌธ์ ๋ฅผ ์ฝ์ด๋ณด๋ฉด "๊ฑฐ์ ์์"๋ ์์์ ๊ฑฐ๋ญ์ ๊ณฑ์๋ค.
๋ฐ๋ผ์ ์ด๋ค ์์๋ฅผ K๋ผ๊ณ ํ์๋ K * K <= B ๋ฅผ ๋ง์กฑํด์ผํ๋ฏ๋ก ์์ ํ๋ณ์ B์ ์ ๊ณฑ๊ทผ๊น์ง๋ง ์คํํ๋ฉด ๋๋ค.
(์ด๋ ๊ฒ ํด๋ ๋ฉ๋ชจ๋ฆฌ ์ฌ์ฉ๋์ 110536KB์๋ค...^^)
์ด ์ธ์๋ ํน๋ณํ ๋ก์ง์ด ํ์์๋ ๋ฌธ์ ๋ค.
๋จผ์ ์๋ผํ ์คํ ๋ค์ค์ ์ฒด ์๊ณ ๋ฆฌ์ฆ๋๋ก ์์ ํ๋ณ์ ํ๊ณ , ํด๋น ์๋ฅผ ์ ๊ณฑ๋ถํฐ ๊ณฑํด๊ฐ๋ฉฐ A์ด์ B์ดํ๊ฐ ๋ ๊ฒฝ์ฐ์๋ง ์นด์ดํธํ๋ค.
2 → 4, 8, 16...
3 → 9, 27, 81...
์ ์ฒด ์ฝ๋
# ๋ฉ๋ชจ๋ฆฌ: 110536KB / ์๊ฐ: 3384ms
from sys import stdin
input = stdin.readline
A, B = map(int, input().split())
# ์ด์ฐจํผ ์ด๋ค ์ i๊ฐ ์์์ผ๋, i*i๋ B๋ณด๋ค ๊ฐ๊ฑฐ๋ ์์์ผํ๋ฏ๋ก "์์ ํ์ "์ B์ ์ ๊ณฑ๊ทผ๊น์ง๋ง ์งํํ๋ฉด ๋๋ค.
root = int(B ** 0.5)
primes = [True] * (root + 1)
primes[0] = primes[1] = False
almost_prime = 0
for i in range(2, root + 1):
if primes[i]:
for j in range(i*i, root + 1, i):
primes[j] = False
x = i*i
while x <= B:
if x >= A:
almost_prime += 1
x *= i
print(almost_prime)
์ฌ์ค "์ ๊ณฑ"์ธ ์๋ง ๊ตฌํ๋ ์ค ์๊ณ ๋ง์ํ?๋ง ๋ฐ๋ณตํ๋ค^^; ๋ค์๋ณด๋ ์ฒซ์ค์์๋ถํฐ N์ ๊ณฑ(N >= 2)์ด๋ผ ๋์ด์๋๋ผ. ๋ฌธ์ ๋ฅผ ์ ์ฝ์...