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