埃拉托色尼筛子python

以下是一个简单的Python程序，用于生成埃拉托色尼筛子：

def sieve(n):
    """
    生成埃拉托色尼筛子
    """
    primes = [True] * (n + 1)
    primes[0] = primes[1] = False
    for i in range(2, int(n ** 0.5) + 1):
        if primes[i]:
            for j in range(i ** 2, n + 1, i):
                primes[j] = False
    return [i for i in range(n + 1) if primes[i]]

# 测试
print(sieve(30))

输出：

[2, 3, 5, 7, 11, 13, 17, 19, 23, 29]

该程序使用了埃拉托色尼筛子算法，首先创建一个长度为n+1的布尔数组，初始值为True，表示该位置上的数是素数。然后从2开始遍历数组，如果该位置上的数是素数，则将其倍数的位置上的数标记为非素数。最后遍历数组，将所有标记为素数的数存入一个列表中返回。

相关问题

埃拉托色尼筛选法python计算次数

埃拉托色尼筛选法是一种用于求解质数的算法，其计算次数与筛选的范围和选择的实现方式有关。以下是一个简单的实现，其中使用了一个数组标记每个数是否为质数：

def eratosthenes(n):
    is_prime = [True] * (n+1)
    is_prime[0] = is_prime[1] = False
    for i in range(2, int(n**0.5)+1):
        if is_prime[i]:
            for j in range(i*i, n+1, i):
                is_prime[j] = False
    return [i for i in range(n+1) if is_prime[i]]

在这个实现中，首先初始化了一个长度为n+1的布尔数组is_prime，用于标记每个数是否为质数，初始值均为True。然后从2开始，依次判断每个数是否为质数，如果是，则将其所有的倍数标记为非质数。最后返回所有标记为质数的数。

对于这个实现，其计算次数大约为O(nloglogn)，其中loglogn是所有小于n的质数个数的对数。这个时间复杂度可以通过更优秀的实现方式进一步优化。

埃拉托色尼筛选法c语言

埃拉托色尼筛选法是一种用于求解素数的算法，其基本思想是先将所有数都标记为素数，然后从2开始，将其所有的倍数标记为合数，重复这个过程，直到所有的数都被标记过。

以下是C语言实现埃拉托色尼筛选法的代码：

#include <stdio.h>

void sieve(int n) {
    // 初始化数组，将所有数都标记为素数
    int prime[n+1];
    for (int i = 0; i <= n; i++) {
        prime[i] = 1;
    }
    
    // 从2开始，将其所有的倍数标记为合数
    for (int p = 2; p * p <= n; p++) {
        if (prime[p] == 1) {
            for (int i = p * p; i <= n; i += p) {
                prime[i] = 0;
            }
        }
    }
    
    // 输出素数
    for (int p = 2; p <= n; p++) {
        if (prime[p] == 1) {
            printf("%d ", p);
        }
    }
}

int main() {
    int n;
    printf("Enter the value of n: ");
    scanf("%d", &n);
    printf("The prime numbers smaller than or equal to %d are: \n", n);
    sieve(n);
    return 0;
}

在这个代码中，我们首先定义了一个函数`sieve`来实现筛选法，该函数接受一个整数`n`作为参数。在函数中，我们首先初始化一个长度为`n+1`的数组`prime`，将其所有的元素都标记为素数。然后，我们从2开始，将其所有的倍数标记为合数。最后，我们输出所有标记为素数的数。

在`main`函数中，我们首先获取用户输入的一个整数`n`，然后调用`sieve`函数来求解小于等于`n`的所有素数。