时间戳

首页 > 解决方案 > 查找最近的素数python

python - 查找最近的素数python

问题描述

我想找到最大的素数range(old_number + 1 , 2*old_number)

到目前为止，这是我的代码：

def get_nearest_prime(self, old_number):
    for num in range(old_number + 1, 2 * old_number) :
        for i in range(2,num):
            if num % i == 0:

                break

    return num

当我调用get_nearest_prime(13) 正确的输出应该是23，而我的结果是25。任何人都可以帮我解决这个问题吗？帮助将不胜感激！

标签： pythonpython-3.x

解决方案

您可以进行很多更改，但您应该进行哪些更改取决于您想要完成的任务。就目前而言，您的代码最大的问题是您成功地用 识别素数，break然后对这些信息不做任何事情。这是一个做大致相同的事情的最小更改。

def get_nearest_prime(old_number):
    largest_prime = 0
    for num in range(old_number + 1, 2 * old_number) :
        for i in range(2,num):
            if num % i == 0:
                break
        else:
            largest_prime = num
    return largest_prime

我们使用largest_prime局部变量来跟踪您找到的所有素数（因为您以递增的顺序遍历它们）。else每当您“正常”退出内部for循环（即，不点击该子句break）时，都会触发该子句。换句话说，任何时候你都找到了一个素数。

这是一个稍微快一点的解决方案。

import numpy as np

def seive(n):
    mask = np.ones(n+1)
    mask[:2] = 0
    for i in range(2, int(n**.5)+1):
        if not mask[i]:
            continue
        mask[i*i::i] = 0
    return np.argwhere(mask)

def get_nearest_prime(old_number):
    try:
        n = np.max(seive(2*old_number-1))
        if n < old_number+1:
            return None
        return n
    except ValueError:
        return None

它的作用大致相同，但它使用一种称为“埃拉托色尼筛法”的算法来加快寻找素数的速度（与您使用的“试除法”相反）。它不是世界上最快的 Sieve，但无需太多调整即可合理理解。

在任何一种情况下，如果您多次调用它，您可能想要跟踪您找到的所有素数，因为计算它们的成本很高。Python 中的缓存既简单又灵活，如果您确实需要提高速度，有很多方法可以实现这一点。

请注意，我不肯定您指定的范围始终包含素数。很有可能，如果是这样，您可以使用更短的代码。类似于以下内容。

def get_nearest_prime(old_number):
    return np.max(seive(2*old_number-1))

我不完全同意您选择的名称，因为该区间中最大的素数通常不是最接近 的素数old_number，但我认为无论如何这就是您要寻找的。

推荐阅读