047. 不同的质因数(distinct primes factors)

第一个有两个不同质因数的两个相邻整数是:

$$ 14=2\times7\\ 15=3\times5 $$
第一个有三个不同质因数的三个相邻整数是:
$$ \begin{aligned} 644&=2^2\times7\times23\\ 645&=3\times5\times43\\ 646&=2\times17\times19 \end{aligned} $$
找到第一个有四个不同质因数的四个相邻整数,求这四个整数中的第一个。

分析:首先我们可以想到一个整数如果要有四个不同的质因数,它至少应该大于2,3,5,7的乘积也就是210,因此最先想到的思路是从210开始逐个求出每个合数的质因数个数,如果连续发现了四个有四个不同质因数的合数,则其中第一个数就是题目的答案。但是我们还可以进行进一步优化,考虑相邻两个质数之间的间隔,如果这个间隔小于或等于四,则这个间隔内无法放下四个连续的合数,因此这个间隔中的合数肯定不满足题目要求,这样我们可以排除掉一大批合数,缩小筛选的范围。对于间隔大于四的两个质数,我们对间隔中的合数逐个求其质因数个数,如果发现了四个连续的有四个不同质因数的合数,则其中第一个即为所求。如果在这些合数中没有找到,则我们再以下一个质数为起点,重复上面的过程,只到找到满足要求的四个合数。我们首先编写一个函数计算特定列表中满足要求的第一个数,如果有则返回它,如果没有则返回假。然后利用上面的思路,在相邻质数之间的合数中来寻找满足要求的数。代码如下:

from sympy import primefactors,nextprime

def first_int(arr):
    f = lambda x : len(primefactors(x))
    for i in range(len(arr)-3):
        if f(arr[i])==4 and f(arr[i+1])==4 and f(arr[i+2])==4 and f(arr[i+3])==4:
            return arr[i]
    return False

def main():
    p = 211
    while True:
        nextp = nextprime(p)
        if (nextp - p) > 4:
            ans = first_int(range(p+1,nextp))
            if ans != False:
                return ans
        p = nextp