python经典百题之求10000之内的素数

题目：求10000之内的素数

程序分析

求10000之内的素数是一个常见的问题。素数是大于1且只能被1和自身整除的整数。我们可以使用循环遍历10000以内的每个数，判断其是否是素数。

方法1: 简单遍历法

遍历2到10000之间的每个数，判断其是否为素数。从2开始，依次将当前数除以2、3、4、…、它本身的前一个数，若能被整除，则不是素数。

def is_prime(num):
    if num < 2:
        return False

    for i in range(2, num):
        if num % i == 0:
            return False

    return True

def find_primes_simple(limit):
    primes = []
    for i in range(2, limit + 1):
        if is_prime(i):
            primes.append(i)
    return primes

# Find primes up to 10000
primes_simple = find_primes_simple(10000)
print("Prime numbers up to 10000:", primes_simple)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

方法2: 优化遍历法

遍历2到10000之间的每个数时，只需判断是否能被2到sqrt(n)之间的数整除，可减少循环次数。

import math

def is_prime(num):
    if num < 2:
        return False

    sqrt_num = int(math.sqrt(num))
    for i in range(2, sqrt_num + 1):
        if num % i == 0:
            return False

    return True

def find_primes_optimized(limit):
    primes = []
    for i in range(2, limit + 1):
        if is_prime(i):
            primes.append(i)
    return primes

# Find primes up to 10000
primes_optimized = find_primes_optimized(10000)
print("Prime numbers up to 10000:", primes_optimized)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

方法3: 埃拉托斯特尼筛法

利用埃拉托斯特尼筛法可以更高效地找出素数。该方法是一种筛选法，从2开始，依次排除2的倍数、3的倍数、4的倍数，直至sqrt(n)。

def sieve_of_eratosthenes(limit):
    is_prime = [True] * (limit + 1)
    is_prime[0] = is_prime[1] = False

    p = 2
    while (p * p <= limit):
        if is_prime[p]:
            for i in range(p * p, limit + 1, p):
                is_prime[i] = False
        p += 1

    primes = [i for i in range(2, limit + 1) if is_prime[i]]
    return primes

# Find primes up to 10000
primes_eratosthenes = sieve_of_eratosthenes(10000)
print("Prime numbers up to 10000:", primes_eratosthenes)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

解题思路及优缺点

• 简单遍历法:
  • 优点:
    • 简单易懂，实现直接。
  • 缺点:
    • 效率较低，需要对每个数都进行多次除法运算。
• 优化遍历法:
  • 优点:
    • 减少了循环次数，只需判断2到sqrt(n)的数即可。
  • 缺点:
    • 仍然需要进行除法运算。
• 埃拉托斯特尼筛法:
  • 优点:
    • 最高效的方法，只需进行一次筛选，不需要除法运算。
  • 缺点:
    • 需要额外空间存储每个数是否为素数。

总结推荐

推荐使用埃拉托斯特尼筛法，它是最高效的方法，只需要进行一次筛选即可找出素数。虽然需要额外的空间存储素数信息，但可以大大提高计算效率，特别是在大数范围内。