如果我要求100000000到100000100之间的质数，有什么高效的算法？

33 2025-09-03 08:58

要高效地找到100000000到100000100之间的质数，由于这个范围很小（只有101个数），推荐使用试除法（trial division）结合预计算的小质数列表。具体步骤如下：

预计算所有小于等于10000的质数：因为100000100的平方根约为10000.0005，所以只需要检查这些质数是否能整除目标数。使用埃拉托斯特尼筛法（Sieve of Eratosthenes）生成10000以内的质数列表，这是一个高效的方法。
检查每个数：对于100000000到100000100之间的每个数，用预计算的质数列表进行试除。如果没有任何质数能整除该数，则该数为质数。

这种方法的时间复杂度很低，因为每个数只需要检查约1229个质数（10000以内的质数数量），总操作次数约为101 * 1229 ≈ 124,129次，在现代计算机上可以在毫秒级完成。

以下是Python代码实现：

python

def sieve(n):
    """生成小于等于n的质数列表 using Sieve of Eratosthenes"""
    is_prime = [True] * (n + 1)
    is_prime[0] = is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if is_prime[i]:
            for j in range(i * i, n + 1, i):
                is_prime[j] = False
    primes = [i for i, prime in enumerate(is_prime) if prime]
    return primes

def is_prime(n, primes):
    """检查n是否为质数，使用预计算的质数列表"""
    if n < 2:
        return False
    limit = int(n**0.5) + 1
    for p in primes:
        if p > limit:
            break
        if n % p == 0:
            return False
    return True

# 预计算10000以内的质数
primes_list = sieve(10000)

# 检查100000000到100000100之间的质数
start = 100000000
end = 100000100
results = []
for num in range(start, end + 1):
    if is_prime(num, primes_list):
        results.append(num)

print("100000000到100000100之间的质数有：")
print(results)

运行上述代码，可以得到结果：

text

100000000到100000100之间的质数有：
[100000007, 100000037, 100000039, 100000049, 100000073, 100000081]

因此，100000000到100000100之间的质数有：100000007, 100000037, 100000039, 100000049, 100000073, 100000081。

这种方法高效且简单，适用于小范围的质数查找。如果范围更大，可以考虑使用分段筛或其他高级算法，但针对当前问题，上述方法是最合适的。

质数

博客

如果我要求100000000到100000100之间的质数，有什么高效的算法？

全部评论

分类

热门文章

Tags

关于