179. 连续正因子(Consecutive positive divisors)

求满足\(1<n<10^7\)\(n\)\(n+1\)拥有相同数目的正因子的整数\(n\)的个数。例如,14有四个正因子,分别为1,2,7,14,而15也有四个正因子,分别为1,3,5,15。

分析:在之前的几道题目中,我们都涉及到了求正整数因子数量的问题。这道题要求找到范围内所有相邻的且拥有因子数量相同的正整数的个数,因此需要我们把范围内所有正整数的因子个数都计算出来。一种自然的思路是使用之前介绍过的计算因子数量的方法计算每个正整数的因子数,这需要我们对每个整数进行质因数分解,再根据各个质因数的幂来计算。显然这种方法在数据范围较大时效率较低,对于题目中给定的范围,这种方法几乎不可能在可接受的时间内得到答案。

另一种更可取的思路是对传统的求特定范围内的质数的筛法进行改进,让它可以用来求解整数的因子数量。例如对于不大于十的正整数,我们可以生成一个长度为十的列表,所有元素都初始化为一,然后从二开始往上筛选,对于所有二的倍数都累加一,也就是把它的因子数累加一;同理,对于所有三的倍数、四的倍数等等也分别累加一,一直遍历到十为止,最后列表中的数字即为每个整数对应的因子数。

上述思路还可以进一步优化,显然对于非完全平方数\(n\),它有一半的因子小于\(\sqrt{n}\),一半的因子大于\(\sqrt{n}\),因为因子总是成对出现的,所以\(n\)的总因子数是它小于\(\sqrt{n}\)的因子数的两倍,必定为一个偶数。所以对于大于一的自然数,其因子数必然不小于二,因此我们可以把创建的列表中二及以上的数字的因子数初始化为二。如果总的数据范围为\(N\),则范围内所有数字的一半的因子都可以在\(\sqrt{N}\)范围内找到,因此对于数\(n\),只需要遍历\(\left[ n,\lfloor \sqrt{N} \rfloor \right]\)范围内整数就足够了。这又分两种情况:对于\(n^2\),由于是一个平方数,我们需要在它的因子数量上累加一;而在\(N\)范围内的数\(n\)的其它倍数分别为\(n\left( n+1 \right) ,n\left( n+2 \right) \cdots ,n\cdot \lfloor N/n \rfloor\),也就是倍数的取值范围为\(\left[ n+1,\lfloor N/n \rfloor \right]\)内的整数。

使用上述方法求解特定范围内整数的因子数量后,我们只需要计算这个列表的一阶差分,也就是让列表中的相邻元素后前相减,如果两个相邻整数的因子数量相同,则相减的元素也为零,最后我们只需要统计计算差分后的列表中为零的元素的个数,即为题目所求。最后,我们调用了\(numba\)模块中的\(njit\)装饰器来为计算因子数量的函数加速,最后的执行时间在我的电脑上约为一秒种左右。代码如下:

# time cost = 1.16 s ± 7.57 ms

import numpy as np
from numba import njit

@njit
def number_of_divisors(N):
    nod = np.array([0,1]+[2]*(N-1))
    u = int(N**0.5)
    for i in range(2,u+1):
        nod[i*i] += 1
        for j in range(i+1,N//i+1):
            nod[i*j] += 2
    return nod

def main(N=10**7):
    nod = number_of_divisors(N)
    diff = np.diff(nod)
    res = N - np.count_nonzero(diff)
    return res