def count_prime_v0(n):
sq = math.isqrt(n)
beg = sq - 1 if n // sq == sq else sq
vals = [n // x for x in range(1, sq + 1)] + list(range(beg, 0, -1))
dp = {v: v - 1 for v in vals}
for m in numtheory.prime_list(sq):
for v in vals:
if m * m > v:
break
dp[v] -= dp[v // m] - dp[m - 1]
return dp[n]def count_prime_v1(n):
sqrt = math.isqrt(n)
a = [0] + list(range(sqrt)) # a[i] = dp[i]
b = [0] + [n // x - 1 for x in range(1, sqrt + 1)] # b[i] = dp[n//i]
for m in range(2, sqrt + 1):
pi = a[m - 1]
if a[m] > pi: # m is prime
m_sq = m * m
for j in range(1, sqrt + 1):
v = n // j
if v < m_sq:
break
x = v // m
b[j] -= (a[x] if x <= sqrt else b[n // x]) - pi
for v in range(sqrt, 0, -1):
if v < m_sq:
break
a[v] -= a[v // m] - pi
return b[1]def count_prime_v2(n):
sqrt = math.isqrt(n)
a = [0] + list(range(sqrt)) # a[i] = dp[i]
b = {x: n // x - 1 for x in range(1, sqrt + 1)} # b[i] = dp[n//i]
for m in range(2, sqrt + 1):
pi = a[m - 1]
if a[m] > pi: # m is prime
m_sq = m * m
for j in b:
v = n // j
if v < m_sq:
break
x = v // m
b[j] -= (a[x] if x <= sqrt else b[n // x]) - pi
for x in range(m, sqrt, m):
if x in b:
del b[x]
for v in range(sqrt, 0, -1):
if v < m_sq:
break
a[v] -= a[v // m] - pi
return b[1]def count_prime_o3(n):
sqrt = math.isqrt(n)
a = [0] + list(range(sqrt)) # a[i] = dp[i]
for v in range(sqrt, 3, -1):
a[v] -= a[v // 2]
b = {j: (n // j) - (n // (j + j)) for j in range(1, sqrt + 1, 2)}
for m in range(3, sqrt + 1, 2):
pi = a[m - 1]
if a[m] > pi: # m is prime
m_sq = m * m
for j in b:
v = n // j
if v < m_sq:
break
b[j] -= (a[v // m] if m * j > sqrt else b[m * j]) - pi
for x in range(m, sqrt, m):
if x in b:
del b[x]
for j in range((sqrt - 1) // m, m - 1, -1):
c = a[j] - pi
e = min((j + 1) * m, sqrt)
for i in range(j * m, e):
a[i] -= c
return b[1]구현체들..
3 - 둘다 기본적으로는 동일한 방식. 구현 디테일만 다르다. c++의 최적 코드를 파이썬으로 번역한 느낌
prime_count_v0_0: TLE - 알고리즘 그대로 옮김. 토글링도 안함
count_prime_v0: 2.160 / 12.182s 토글링 적용. dict로 dp 테이블을 저장
count_prime_v1: 1.520 / 7.921s 리스트로 dp 테이블 저장. 에라체 전처리 제거.
count_prime_lucy: 1.263s / 6.664s V1을 기술적으로 최적화.
count_prime_o1(n) 0.626s / 3.675s v1에서 불필요한 b배열 계산 제거. b배열은 dict로 구현
count_prime_o2 ??? / 2.941s o1에서 2-wheel 적용
count_prime_o3 ??? / 2.489s o2에서 small 배열 계산 최적화
count_prime_o4 ??? / 1.828s o3에서 del 범위 줄임