用筛选法求100以内的素数

以下是用筛选法求100以内的素数的代码：

def sieve_of_eratosthenes(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*i, n+1, i):
                primes[j] = False
    return [i for i in range(n+1) if primes[i]]

print(sieve_of_eratosthenes(100))

输出结果为：[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]

相关问题

用筛选法求100以内素数

以下是Python代码实现：

# 初始化所有数字为素数
is_prime = [True] * 101

# 0和1不是素数
is_prime[0] = is_prime[1] = False

# 从2开始枚举，筛选出素数
for i in range(2, 101):
    # 如果当前数字已经被标记为非素数，则跳过
    if not is_prime[i]:
        continue

    # 枚举当前素数的倍数并标记为非素数
    for j in range(i * 2, 101, i):
        is_prime[j] = False

# 输出所有素数
for i in range(2, 101):
    if is_prime[i]:
        print(i, end=' ')

输出结果为：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

C语言用筛选法求100以内素数

筛选法求100以内素数的C语言代码如下：

#include <stdio.h>

int main() {
    int i, j;
    int is_prime[101]; // 用数组记录是否为素数，0为素数，1为合数

    // 初始化数组，假设所有数都是素数
    for (i = 2; i <= 100; i++) {
        is_prime[i] = 0;
    }

    // 筛选合数
    for (i = 2; i <= 50; i++) {
        if (is_prime[i] == 0) { // i是素数，筛选i的倍数
            for (j = i * 2; j <= 100; j += i) {
                is_prime[j] = 1; // j是i的倍数，标记为合数
            }
        }
    }

    // 输出素数
    printf("100以内的素数有：\n");
    for (i = 2; i <= 100; i++) {
        if (is_prime[i] == 0) {
            printf("%d ", i);
        }
    }
    printf("\n");

    return 0;
}

代码思路：

首先用一个数组is_prime记录每个数是否为素数，初始化所有数都为素数。然后从2开始，依次筛选合数。如果当前数i是素数，则将i的倍数标记为合数，即is_prime[j] = 1。最后输出素数即可。

运行结果：

100以内的素数有：
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