用筛法求素数

Input

一个数N (1<N<1000000)

Output

以空格隔开的素数。

Sample Input

10

Sample Output

2 3 5 7

python解法

n = int(input("请输入一个整数n: "))  # 读取用户输入的整数n

# 初始化一个布尔数组 "prime[0..n]"，并假设所有元素都是素数
prime = [True] * (n+1)
prime[0] = prime[1] = False  # 0和1不是素数

p = 2
while p * p <= n:
    # 如果 prime[p] 没有改变，那么它是一个素数
    if prime[p]:
        # 更新所有p的倍数
        for i in range(p * p, n+1, p):
            prime[i] = False
    p += 1

# 收集所有素数
for p in range(2, n+1):
    if prime[p]:
        print(p, end=" ")

c++解法

#include<bits/stdc++.h> // 引入标准库头文件，包含了大多数常用库
using namespace std;    // 使用标准命名空间，避免反复写std::

bool a[1000000] = {0};  // 定义一个布尔数组a，初始化为0，用于标记素数

int main() {
    int n;
    cin >> n; // 读取用户输入的整数n

    // 初始化：0和1不是素数
    a[0] = 1; // 0不是素数
    a[1] = 1; // 1不是素数

    // 筛法寻找素数
    for (int i = 2; i <= n; i++) { // 遍历从2到n的所有整数
        if (a[i] == 0) { // 如果a[i]为0，表示i是素数
            cout << i << " "; // 输出素数i

            // 将i的所有倍数标记为非素数
            for (int j = 2; j * i <= n; j++) {
                a[j * i] = 1; // 标记i的倍数为非素数
            }
        }
    }

    return 0; // 程序正常结束
}