时间戳

首页 > 解决方案 > 如何从素数列表中获取不同的因子？

python - 如何从素数列表中获取不同的因子？

问题描述

我一直在尝试问题 47（欧拉项目），问题如下：

具有两个不同质因数的前两个连续数字是：

14 = 2 × 7
15 = 3 × 5

具有三个不同质因数的前三个连续数字是：

644 = 2² × 7 × 23
645 = 3 × 5 × 43
646 = 2 × 17 × 19.

找到前四个连续整数，每个整数都有四个不同的素因数。这些数字中的第一个是什么？

这是我的方法：（您可能需要（pip）安装 sympy）

import time
import sympy

start=time.time()
a=list(sympy.primerange(1,101))

b=[] 

for i in range(646,100000):
    c=[]
    for j in a:
        if i%j==0:
            c.append(j)
            if len(c)==4:
                s=[str(o) for o in c]
                res=int("".join(s))
                b.append(res)
            else:
                pass
        else:
            pass

print(b[:4])
end=time.time()
print(end-start)

我如何实现因素应该不同的逻辑？我现在得到的答案（这显然是错误的）是：23511 正确答案是：134043

sympy 素数基本功能：https ://www.geeksforgeeks.org/prime-functions-python-sympy

谢谢 ！

标签： pythonlistmathsympy

解决方案

好的，假设您有一个函数可以为您提供主要因素

def find_4_diff(i):
    fact_i = find_factors(i)
    fact_i_plus_1 = find_factors(i+1)
    if all([f_i not in f_i_plus_1 for i in fact_i]):
        fact_i_plus_2 = find_factors(i+2)
        if all([f_i not in f_i_plus_2 for i in fact_i]) and  all([f_i not in f_i_plus_2 for i in fact_i_plus_1]):
            fact_i_plus_3 = find_factors(i+3)
            if all([f_i not in fact_i_plus_3 for i in fact_i]) and  all([f_i not in fact_i_plus_3 for i in fact_i_plus_1]) and all([f_i not in fact_i_plus_3 for i in fact_i_plus_2]):
                return i
    return 


i = 646
myval = find_4_diff(i)
while  myval is None:
    i += 1
    myval = find_4_diff(i)
print(i)

现在您可以考虑优化的方法：例如，如果因子 i+1 与因子 i+2 无效，您总是至少计算 i+1 的因子，因此不需要再次计算（可以将其作为参数传递）你可以跳过 i+1 等

您所需要的只是一个将数字的因子作为数字返回的函数，例如 2 到 3 返回为 8 等

推荐阅读