时间戳

首页 > 解决方案 > 给定一个数字 n 找到最接近它的质数，最大偶数位数

python - 给定一个数字 n 找到最接近它的质数，最大偶数位数

问题描述

我很难找到最接近具有最大偶数位数的任何给定整数 n 的素数。下面的代码有效并通过了所有示例测试。但是当数字变得太大时，它就会超时。谁能建议我如何优化它？

from collections import defaultdict


def is_prime(n):
    first, i = 1, 2
        if n <= first:
            return False
    while i <= (n**0.5):
        if n % i == 0:
            return False
        i += first
    return True


def highest_prime(n):
    dd = defaultdict(int)
    nums = [str(x) for x in reversed(range(n)) if is_prime(x)]
    is_even = (lambda x: x % 2 == 0)
    for outer in nums:
        for inner in outer:
            if is_even(int(inner)):
                dd[outer] += 1
    return max(dd, key=lambda x: dd[x])


if __name__ == "__main__":
    print(highest_prime(1000))
    print(highest_prime(1210))
    print(highest_prime(10000))

测试 1 预期值为 887
测试 2 预期值为 1201
测试 3 预期值为 8887

编辑：根据建议，由于数字中素数的最大数量总是比总数字少一，我只保留了那些长度与给定整数 N 相同的数字。但它仍然不是不够快。对于素数检查，我使用了isPrime Function for Python Language的选定答案

def highest_prime(n):
    nums = list(range(n))
    temp = []
    for x in range(len(nums)):
        if len(str(nums[x])) == len(str(nums[-1])):
            if is_prime(nums[x]):
                temp.append(str(nums[x]))
    is_even = (lambda x: x % 2 == 0)
    dd = defaultdict(int)
    for outer in temp[::-1]:
        for inner in outer:
            if is_even(int(inner)):
                dd[outer] += 1
    return max(dd, key=lambda x: dd[x])

还有其他建议吗？谢谢！

标签： pythonpython-3.x

解决方案

有非常聪明的方法可以测试一个数字是否为素数（或者至少聪明的方法在非常大的 N 范围内是正确的）但是在这种情况下，当你计算所有素数到某个数字时，你可以使用前一个素数数字，只检查它们作为因素：

def get_primes_list(n):
    if n < 2:
        return []
    primes = [2]
    for i in range(3,n+1):
        sqroot = i**0.5
        for p in primes:
            if i%p == 0:
                break
            if p > sqroot:
                primes.append(i)
                break
    return primes

如果您正在寻找比这更有效的方法（因为这种方法仍然消耗资源，并且当您达到数千万时仍然需要很长时间）您最好的选择是找到一个有效的素性测试的现有实现，例如提到的 Rabin-Miller 素数检验

推荐阅读