python - 用于查找数字的最大素数的 python 代码问题(Project Euler 问题 3)
问题描述
我目前正在尝试使用 python 解决Project Euler 问题 3,它试图找到一个数字的最大素数。我正在使用的方法本质上是强制通过每个小于所讨论整数的整数,检查它是否是所述整数的因子,然后检查它是否是素数。但是,由于某种原因,我的代码似乎无法正常工作。
我尝试使用创建一个函数,该函数遍历小于给定整数 (n) 的每个整数 (i),如果 i 可被 n 整除,则该函数继续通过遍历每个整数来检查 i 是否为质数小于或等于 i (x) 的整数。如果 x 是 i 的因子,则将该值添加到定义为 (a) 的零整数。之后,如果 a 最终等于 i + 1,则意味着该因子是素数,因为唯一可整除的数字是它自己和 1。代码如下:
def primefactor(n):
for i in range(1, n+1): #goes through each integer less than n
if n % i == 0: #checks if integer is a factor
for x in range(1, i+1): #another loop to check if the factor is prime
a = 0
primenumbers = []
if i % x == 0:
a += x
if a == i + 1:
primenumbers.append(i)
print(primenumbers)
primefactor(13195)
我期望的输出是它打印一个数字的所有主要因素的列表,在这种情况下[5, 7, 13, 29]
,但是,我得到的只是一个空列表,[]
解决方案
您的代码的这个问题是您primenumbers
每次迭代都使用primenumbers = []
.
此外,如果您不想强行使用它,解决此类解决方案的一个好方法是搜索一个公式,例如素数公式,您会发现:
根据威尔逊定理,
n+1
当且仅当 是素数n! mod(n + 1) = n
。
所以你可以做这样的事情:
# This is just used as caching to make it faster
# it is not needed.
from functools import lru_cache
from math import factorial
@lru_cache()
def isprime(x):
n = x - 1
if n == factorial(n) % (n + 1):
return True
else:
return False
def primefactor(n):
primenumbers = []
for i in range(1, n + 1): #goes through each integer less than n
if n % i == 0: #checks if integer is a factor
isprime(i) and primenumbers.append(i)
print(primenumbers)
primefactor(13195)
输出:
[1, 5, 7, 13, 29]
还有比这个更快的解决方案,它确实会遍历所有数字 0 到n
:
找到数字的最大素数的算法
推荐阅读
- powerbi - 无法计算 power bi 中列总数的百分比
- java - 递归霍夫曼解码函数不退出函数
- docker - 如何访问或将主机文件传递给 Docker Python 脚本
- sql - 如何查找字符在字符串中出现的连续次数
- android - 如何在 facebook graph api 中获取 user_posts 的访问权限
- vue.js - 如何使 Vuex 对列表内对象的属性/属性更改做出反应
- java - 在java中上传内容类型为application / octet-stream的文件?
- mysql - 仅使用 1 个语句从 2 个具有条件的表创建列表
- html - 如何防止 Angular 中的选项卡事件?
- reactjs - 阻止反应路线