[已解决]c++筛选法求2到1000的素数

王鹿其

最佳答案

月排行榜 / 总排行榜

isdkz

2023-10-28 11:32:49

你可以使用筛选法来求解2到1000之间的素数。筛选法是一种常见的算法，它通过不断筛选掉非素数来找出素数。

首先，你需要创建一个长度为1001的布尔数组，用来标记每个数字是否为素数。将数组中的所有元素初始化为true，表示所有数字都是素数。

然后，从2开始，遍历数组中的每个数字。如果当前数字为素数（即数组中对应位置的值为true），则将该数字的所有倍数标记为非素数（即将数组中对应位置的值设为false）。

最后，遍历数组中的数字，将值为true的数字输出即可，它们就是2到1000之间的素数。

下面是用C++实现的代码示例：

#include <iostream>
#include <vector>

using namespace std;

vector<int> findPrimes(int n) {
    vector<bool> isPrime(n+1, true);
    vector<int> primes;

    for (int i = 2; i <= n; i++) {
        if (isPrime[ i]) {
            primes.push_back(i);
            for (int j = i*2; j <= n; j += i) {
                isPrime[j] = false;
            }
        }
    }

    return primes;
}

int main() {
    vector<int> primes = findPrimes(1000);

    for (int prime : primes) {
        cout << prime << " ";
    }
    cout << endl;

    return 0;
}

这段代码会输出2到1000之间的所有素数。你可以根据需要修改代码中的参数来求解不同的范围内的素数。

跳转到最佳答案楼层

isdkz

你可以使用筛选法来求解2到1000之间的素数。筛选法是一种常见的算法，它通过不断筛选掉非素数来找出素数。

首先，你需要创建一个长度为1001的布尔数组，用来标记每个数字是否为素数。将数组中的所有元素初始化为true，表示所有数字都是素数。

然后，从2开始，遍历数组中的每个数字。如果当前数字为素数（即数组中对应位置的值为true），则将该数字的所有倍数标记为非素数（即将数组中对应位置的值设为false）。

最后，遍历数组中的数字，将值为true的数字输出即可，它们就是2到1000之间的素数。

下面是用C++实现的代码示例：

#include <iostream>
#include <vector>

using namespace std;

vector<int> findPrimes(int n) {
    vector<bool> isPrime(n+1, true);
    vector<int> primes;

    for (int i = 2; i <= n; i++) {
        if (isPrime[ i]) {
            primes.push_back(i);
            for (int j = i*2; j <= n; j += i) {
                isPrime[j] = false;
            }
        }
    }

    return primes;
}

int main() {
    vector<int> primes = findPrimes(1000);

    for (int prime : primes) {
        cout << prime << " ";
    }
    cout << endl;

    return 0;
}

这段代码会输出2到1000之间的所有素数。你可以根据需要修改代码中的参数来求解不同的范围内的素数。

陈尚涵

Mike_python小 发表于 2023-10-28 11:33
None

球一个最佳答案谢谢啦！这对我非常重要！

难绷（