如何优化费马小定理计算代码并仅输出真同余结果？

好的，咱们来优化这段和费马小定理相关的代码，同时实现只输出满足同余条件的结果。

1. 替换低效的幂运算方式 #

原代码里的(2 << i - 2)本质是计算2^(i-1)，但这种方式对较大的i会生成超大整数，再取模会浪费大量计算资源。Python内置的pow(base, exp, mod)函数采用快速幂算法，能在计算过程中直接取模，效率提升非常明显，尤其是i较大时。

2. 提前过滤不可能满足条件的数 #

根据数论知识，我们可以提前排除必然不满足条件的i：

• i=1时，任何数模1结果都是0，不可能等于1，直接跳过；
• i是大于2的偶数时，2^(i-1)是偶数，模偶数i的结果必然是偶数，不可能等于1，所以只需检查奇数和i=2。

3. 只输出满足条件的结果 #

不需要打印每个i的判断结果，仅当条件成立时输出i即可。

改进后的代码 #

for i in range(2, 351):
    # 跳过大于2的偶数
    if i > 2 and i % 2 == 0:
        continue
    # 使用高效的模幂运算验证同余条件
    if pow(2, i-1, i) == 1:
        print(i)

额外说明 #

• 要注意：满足2^(i-1) ≡ 1 mod i的数不一定都是质数，这类数被称为伪素数（以2为底），比如i=341就是伪素数（它是合数，341=11×31），但会被这段代码输出。如果想要只输出质数，还需要结合米勒-拉宾测试等更严谨的素性验证方法。
• 如果你用的是Python 2，把print(i)改成print i就能兼容运行。

内容的提问来源于stack exchange，提问作者Hunt's Theorem