南昌做网站哪家最好,中文app开发工具,Wordpress表单无法收到,北京网站平台建设公司题目#xff1a;求10000之内的素数
程序分析
求10000之内的素数是一个常见的问题。素数是大于1且只能被1和自身整除的整数。我们可以使用循环遍历10000以内的每个数#xff0c;判断其是否是素数。
方法1: 简单遍历法
遍历2到10000之间的每个数#xff0c;判断其是否为素…题目求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)的数即可。 缺点: 仍然需要进行除法运算。 埃拉托斯特尼筛法: 优点: 最高效的方法只需进行一次筛选不需要除法运算。 缺点: 需要额外空间存储每个数是否为素数。
总结推荐
推荐使用埃拉托斯特尼筛法它是最高效的方法只需要进行一次筛选即可找出素数。虽然需要额外的空间存储素数信息但可以大大提高计算效率特别是在大数范围内。
