设p,q是两个相邻的素数，那么对满足$p^2 < n < q^2$的n而言，只要n恰好只能被p,q中的一个整除，它就是半可约的。
容易验证$ups(999966663333)=1000003$，因此先用筛法找出不超过1000003的所有素数，再用上述规则遍历求和，结果是$1259187438574927161$。
target=1000004
d=[0]*target
n=2
while n < target:
for i in range(n*n,target,n):
d[i]=d[i]+1
n=n+1
while n < target and d[n]>0:
n=n+1
primeList=[k for k in range(2,target) if d[k]==0]
r=0
for i in range(len(primeList)-1):
p,q=primeList[i],primeList[i+1]
r+=sum(j for j in range(p*p+p,q*q,p) if j%q>0 and j < 999966663334)
r+=sum(j for j in range(q*q-q,p*p,-q) if j%p>0 and j < 999966663334)
print r
|
