时间戳

首页 > 解决方案 > 需要帮助 费马的素数计算

python - 需要帮助 费马的素数计算

问题描述

我需要有关如何完成作业的帮助。我应该用两种不同的方法生成素数：费马小定理和平方根的使用。当我用每种方法生成 3,000,000 个数字时（由于费马的方法不是 100% 正确，素数的数量不同）我应该通过划分两个列表或变量来找到费马方法的准确性（其中所有数字被保存）彼此找到使用第一个母亲而不是平方根的可信度。

这就是我的问题所在。在我的作业中，如果数字与等式匹配，我应该返回值“True”，否则返回 false。不知何故，我需要添加一个列表或变量，同时仍然返回“True”或“False”以保存所有数字，以便最终程序可以计算百分比。我真的不知道如何有效地添加它，我想要一些关于我的代码的反馈，以便我可以改进它。我有点卡在自动取款机上。

https://en.wikipedia.org/wiki/Fermat%27s_little_theorem

作业的依据是什么

我的进步（我只完成了大约 3 个月的编程，因此非常感谢任何建设性的反馈）。

这只是 Fermats 版本。另一个看起来相同，但方程不同。只需要获取一个列表或变量来保存所有为 True 的值：

from time import *

start_time = time()


def is_prime(n):
    fermat = int(pow(2, n - 1, n))
    while n > 1:
        if fermat == 1:
            return True
        return False


for x in range(1, 30001):
    print(x, is_prime(x))
print("Total amount of time:", time()-start_time)

标签： pythonpython-3.x

解决方案

您可以使用列表推导创建一个列表，其中索引是数字，值是该索引的素数。

（还注意到我is_prime进行了一些重构。您不需要fermat变量，而且您绝对不需要while循环）。

def is_prime(n):
    return int(pow(2, n - 1, n)) == 1:

print([is_prime(n) for n in range(1, 30001)])
# [False, False, True, False, True, False, True, ..... ]

需要注意的是 Python 索引从 0 开始。我们可以通过在列表前面加上一个标记值来解决这个问题：

 print([None] + [is_prime(n) for n in range(1, 30001)])
 # [None, False, False, True, False, True, False, True, ..... ]

另一种选择是使用字典，其中键是数字，值是素数，但请记住，在 Python < 3.7 中字典是无序的：

 print({n: is_prime(n) for n in range(1, 30001)})
 # {1: False, 2: False, 3: True, 4: False, 5: True, 6: False, 7: True, ..... }


如果您只对（大概）素数列表感兴趣：

print([n for n in range(1, 30001) if is_prime(n)])
# [3, 5, 7, 11, 13, 17, .... ]

推荐阅读