孪生约数和

求满足

1 < n < 10^{7}

且

n

和

n + 1

的约数数量相同的整数n的总数。例如，14有4个约数1、2、7、14，而15也有4个约数1、3、5、15，因此

n = 14

就是一个满足要求的数。

本题难度:

解答

似乎没什么值得一提的，用筛法求出范围内所有数的质因数，若

n = p_{1}^{a_{1}} \dots p_{k}^{a_{k}},

是n的质因数分解，则显然其约数总数为

(1 + a_{1}) \dots (1 + a_{k})

。直接计算和比较即得结果

986262

。

target=10**7
subTarget=3200

d=[[] for i in range(target)]

n=2

while n < subTarget:
    for i in range(n+n,target,n):
        d[i].append(n)
    n+=1
    while n < subTarget and d[n]:
        n+=1

r=1000
s=1
for n in range(8985,target):
    if d[n]:
        m=n
        t=1
        for p in d[n]:   
            i=1
            while m%p==0:
                m/=p
                i+=1
            t*=i
        if m>1:
            t*=2
        if s==t:
            r+=1
        s=t
    else:
        s=2

print r