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

题目：求10000之内的素数

程序分析

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

方法1: 简单遍历法

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

def is_prime(num):if num < 2:return Falsefor i in range(2, num):if num % i == 0:return Falsereturn Truedef 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)

方法2: 优化遍历法

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

import mathdef is_prime(num):if num < 2:return Falsesqrt_num = int(math.sqrt(num))for i in range(2, sqrt_num + 1):if num % i == 0:return Falsereturn Truedef 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)

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

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

def sieve_of_eratosthenes(limit):is_prime = [True] * (limit + 1)is_prime[0] = is_prime[1] = Falsep = 2while (p * p <= limit):if is_prime[p]:for i in range(p * p, limit + 1, p):is_prime[i] = Falsep += 1primes = [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)

解题思路及优缺点

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

总结推荐

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