求一百以内的素数的编程

一百以内素数的编程实现

素数（质数）是指大于1的自然数，除了1和自身外没有其他正因数。寻找一百以内的素数是编程初学者常见的练习任务。

最基本的实现方法

暴力枚举法

python

prime_numbers = []

for num in range(2, 101):

is_prime = True

for i in range(2, num):

if num % i == 0:

is_prime = False

break

if is_prime:

prime_numbers.append(num)

print("100以内的素数：", prime_numbers)

这个方法虽然直观但效率较低，因为对每个数都要进行全量检查。时间复杂度为O(n²)。

优化方法

简单优化 - 只检查到平方根

数学原理：若数字n不是素数，则至少包含一个不大于√n的因数。

python

import math

prime_numbers = []

for num in range(2, 101):

is_prime = True

for i in range(2, int(math.sqrt(num)) + 1):

if num % i == 0:

is_prime = False

break

if is_prime:

prime_numbers.append(num)

print("100以内的素数：", prime_numbers)

这种方法将时间复杂度降低到O(n√n)。

更高效的算法

埃拉托斯特尼筛法

这是一种筛选素数的高效算法，时间复杂度为O(n log log n)。

python

def sieve_of_eratosthenes(limit):

sieve = [True] * (limit + 1)

sieve[0] = sieve[1] = False

for current in range(2, int(limit 0.5) + 1):

1. 素数定理：在自然数中，素数的分布密度约为1/ln(n)，即数越大，素数越稀疏。

2. 孪生素数：相差2的素数对，如(3,5)、(5,7)、(11,13)等。

3. 梅森素数：形如2^p-1的素数，目前最大的已知素数多为梅森素数。

4. 素数测试：在实际应用中，米勒-拉宾素性测试等概率性算法比确定性算法更高效。

5. 素数的应用：在密码学(RSA算法)、哈希函数、随机数生成等领域有重要应用。

结果验证

一百以内的素数共有25个：

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。