埃拉托色尼筛法伪代码解释
时间: 2024-09-08 08:03:12 浏览: 23
埃拉托色尼筛法(Sieve of Eratosthenes),也被称为素数筛法,是一种古老而高效的找出一定范围内所有质数的算法。以下是简单的伪代码解释:
```python
function sieve_of_eratosthenes(n):
primes = [True] * (n + 1) # 创建一个布尔数组,初始全部标记为质数
primes[0], primes[1] = False, False # 0和1不是质数
for i from 2 to √n: # 遍历到√n,因为大于这个数的所有因子都小于它本身
if primes[i]: # 如果i是质数
for j from i^2 to n with step i: # 将i的倍数标记为合数
primes[j] = False
result = [] # 存储找到的质数
for i from 2 to n:
if primes[i]:
result.append(i)
return result
相关问题
埃拉托色尼筛法伪代码解释C语言
埃拉托色尼筛法,也叫素数筛法,是一种用于找出一定范围内所有质数的经典算法。以下是用C语言实现的一个简单伪代码解释:
```c
// 定义一个数组isPrime用于记录每个数字是否为质数
int isPrime[limit+1] = {0}; // limit是需要筛选的上限
// 初始化值,小于2的数不是质数
for (int i = 2; i <= limit; i++) {
isPrime[i] = 1; // 假设i是质数
}
// 根据埃拉托色尼筛法,从2开始,将它的倍数标记为非质数
for (int i = 2; i * i <= limit; i++) {
if (isPrime[i]) {
for (int j = i * i; j <= limit; j += i) {
isPrime[j] = 0; // 如果j能被i整除,那么j不是质数
}
}
}
// 遍历isPrime数组,打印出所有的质数
for (int i = 2; i <= limit; i++) {
if (isPrime[i]) {
printf("%d ", i); // 如果当前元素表示质数,将其输出
}
}
埃拉托色尼筛法时间复杂度
埃拉托色尼筛法的时间复杂度是O(nlog(logn))。这是因为在该算法中,我们需要遍历从2到n的所有数字,并标记它们的倍数为合数。对于每个素数p,我们需要标记p的倍数,这样的操作需要进行n/p次。因此,总的操作次数可以近似为n/2 + n/3 + n/5 + ... + n/p,其中p为小于等于n的素数。根据数学推导,这个和的上界是nlog(logn)。因此,埃拉托色尼筛法的时间复杂度是O(nlog(logn))。