3种方式获取100以内的质数(Python)

获取100以内的质数可以通过多种方法实现，下面我们将介绍三种常见的方式，分别是暴力法、埃拉托斯特尼筛法（Sieve of Eratosthenes）、以及基于数学性质的方法。每种方法都附带相应的Python代码示例。

方法一：暴力法

暴力法是一种直接的算法，简单易懂。该方法的基本思路是判断每个数是否为质数，通过检查其是否能被小于其平方根的整数整除来实现。如果一个数n不被2到√n之间的任何整数整除，那么它就是质数。

以下是使用暴力法获取100以内质数的代码示例：

def is_prime(num):
    if num < 2:
        return False
    for i in range(2, int(num**0.5) + 1):
        if num % i == 0:
            return False
    return True

def get_primes_via_brute_force(limit):
    primes = []
    for num in range(2, limit):
        if is_prime(num):
            primes.append(num)
    return primes

primes = get_primes_via_brute_force(100)
print("100以内的质数（暴力法）：", primes)

方法二：埃拉托斯特尼筛法

埃拉托斯特尼筛法是一种高效的算法，适合于求取一定范围内的质数。该方法的思路是先假设所有数都是质数，然后从小到大逐步排除合数。具体来说，我们从2开始，标记它的倍数为合数，然后继续寻找下一个未被标记的数，并重复这一过程直到检查到√n。

以下是使用埃拉托斯特尼筛法获取100以内质数的代码示例：

def sieve_of_eratosthenes(limit):
    is_prime = [True] * limit
    is_prime[0] = is_prime[1] = False  # 0和1不是质数
    for num in range(2, int(limit**0.5) + 1):
        if is_prime[num]:
            for multiple in range(num*num, limit, num):
                is_prime[multiple] = False
    primes = [num for num, prime in enumerate(is_prime) if prime]
    return primes

primes = sieve_of_eratosthenes(100)
print("100以内的质数（埃拉托斯特尼筛法）：", primes)

方法三：基于数学性质

如果我们考虑到质数的性质，我们可以优化搜索范围。例如，除了2以外的所有质数都是奇数。这意味着只需检查奇数即可，减少了计算量。同时我们可以用更简化的方式在一个循环中处理。

以下是基于数学性质的方法获取100以内的质数的代码示例：

def is_prime_optimized(num):
    if num < 2:
        return False
    if num == 2:
        return True
    if num % 2 == 0:
        return False
    for i in range(3, int(num**0.5) + 1, 2):
        if num % i == 0:
            return False
    return True

def get_primes_via_math_properties(limit):
    primes = [2]  # 先添加2
    for num in range(3, limit, 2):  # 只检查奇数
        if is_prime_optimized(num):
            primes.append(num)
    return primes

primes = get_primes_via_math_properties(100)
print("100以内的质数（基于数学性质的方法）：", primes)

总结

以上三种方法各有优缺点。暴力法简单直观，但效率较低；埃拉托斯特尼筛法是标准的质数筛选算法，性能优越；而基于数学性质的方法则结合了质数的特性，虽然实现略显复杂，但在某些情况下效率更高。根据需要选择合适的方法，可以更好地满足不同场景下的计算需求。