两素数整除

不超过100的正整数中素因子只有2和3的最大整数是96。

记$M(p,q,N)$为不超过N的正整数中素因子只有p和q的最大整数。若不存在这样的数，则取$M(p,q,N)$为0。

例如$M(2,3,100)=96, M(3,5,100)=75, M(2,73,100)=0$。

给定N，记S(N)为所有相异的$M(p,q,N)$之和，例如$S(100)=2262$。

求$S(10^7)$。

本题难度:

解答

本题非常简单，只需先用筛法找出五百万以下的素数，再枚举所有乘积不超过一千万的素数对p,q，考察$p^aq^b$取最大即可，最终结果是$11109800204052$。

注：代码中打印了进度信息。

import bisect

bound=10**7

target=bound/2
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]

print "prime list generated"

m=len(primeList)
tick=m/100
s=0

for i in range(m):
    k=bisect.bisect(primeList,bound/primeList[i]+1)
    for j in range(i+1,k):
        p=primeList[i]
        r=0
        while p*primeList[j] <= bound:
            q=primeList[j]
            while p*q <= bound:
                r=max(r,p*q)
                q*=primeList[j]
            p*=primeList[i]
        s+=r
    if i%tick==0:
        print i/tick, "percent completed"

print s