<p>我有一个部分的解决方案给你,但结果看起来不太好。。(这个解决方案可能不能给你一个现代计算机硬件的答案(内存的数量目前是有限的))我从<a href="https://codegolf.stackexchange.com/q/26739/42652">this</a>pcg质询中得到了一个答案,并将其修改为从n/phi(n)到特定n的比率</p>
<pre><code>import numba as nb
import numpy as np
import time
n = int(2**31)
@nb.njit("i4[:](i4[:])", locals=dict(
n=nb.int32, i=nb.int32, j=nb.int32, q=nb.int32, f=nb.int32))
def summarum(phi):
#calculate phi(i) for i: 1 - n
#taken from <a>https://codegolf.stackexchange.com/a/26753/42652</a>
phi[1] = 1
i = 2
while i < n:
if phi[i] == 0:
phi[i] = i - 1
j = 2
while j * i < n:
if phi[j] != 0:
q = j
f = i - 1
while q % i == 0:
f *= i
q //= i
phi[i * j] = f * phi[q]
j += 1
i += 1
#divide each by n to get ratio n/phi(n)
i = 1
while i < n: #jit compiled while loop is faster than: for i in range(): blah blah blah
phi[i] = i//phi[i]
i += 1
return phi
if __name__ == "__main__":
s1 = time.time()
a = summarum(np.zeros(n, np.int32))
locations = np.where(a >= 10)
print(len(locations))
</code></pre>
<p>我的公司里只有足够的内存。测试约<code>0 < n < 10^8</code>,最大比值约为6。虽然10^8已经花了几秒钟时间(不确定开销是多少…),但是你可能没有任何运气去达到更大的n。。。斯派德最近表现得很奇怪)</p>