不超过190的素数共有42个，需要找到其中若干项的乘积，使之不超过$m=\lceil\sqrt(p)\rceil$且最大。
直接枚举会有$2^{42}$种可能显然不可行，因此将这42个数分成两组，分别记录每组中各个子集的乘积并排序。
随后遍历第一组，对其中每个元素x，二分查找第二组中满足$xy_y<m$的最大$y_x$，最后输出$xy_x$最大值的后16位，结果是$1096883702440585$。
注：以下为Python 3代码，因math.isqrt, math.prod均为Python 3中的新方法。
import math,itertools,bisect
p=[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,181]
m=math.isqrt(math.prod(p))+1
a=sorted([*{math.prod(c) for k in range(22) for c in itertools.combinations(p[::2],k) if math.prod(c) < m}])
b=sorted([*{math.prod(c) for k in range(22) for c in itertools.combinations(p[1::2],k) if math.prod(c) < m}])
r=0
for x in a:
j=bisect.bisect_left(b,m//x)
while j>=len(b) or x*b[j]>=m:
j-=1
r=max(r,x*b[j])
print(str(r)[-16:])
|
