python求500以内所有的素数

埃拉托色尼筛法（Sieve of Eratosthenes）是一种高效的算法，用于在一定范围内找出所有素数。它的基本思想是：从2开始，标记所有2的倍数为非素数，然后找到下一个未标记的数字，标记它的倍数为非素数，如此反复，直到处理完所有小于等于指定范围内的数字。

具体步骤如下：

1. 初始化列表：创建一个从2到指定范围的所有整数列表。假设列表中的每个数都是素数。

2. 从最小素数开始标记：从第一个素数2开始，标记所有2的倍数为非素数。

3. 找到下一个未标记的数：即下一个素数，并标记它的所有倍数为非素数。

4. 重复步骤2和3：直到遍历到指定范围的平方根为止。因为更大的数如果不是素数，早已被标记。

5. 提取所有素数：所有未被标记的数即为素数。

这个算法的时间复杂度为 $O(n\log \log n)$，适合处理较大范围内的素数求解。

# 使用埃拉托色尼筛法求500以内的所有素数
def sieve_of_eratosthenes(limit):
    sieve = [True] * (limit + 1)
    sieve[0] = sieve[1] = False
    for start in range(2, int(limit**0.5) + 1):
        if sieve[start]:
            for i in range(start*start, limit + 1, start):
                sieve[i] = False
    return [num for num, is_prime in enumerate(sieve) if is_prime]

primes_under_500 = sieve_of_eratosthenes(500)
primes_under_500

500以内的所有素数如下：

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499