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

王鹿其

最佳答案

月排行榜 / 总排行榜

isdkz

2023-10-28 11:32:49

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

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

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

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

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

1. #include <iostream>
   
2. #include <vector>
   
3. 
   
4. using namespace std;
   
5. 
   
6. vector<int> findPrimes(int n) {
   
7.     vector<bool> isPrime(n+1, true);
   
8.     vector<int> primes;
   
9. 
   
10.     for (int i = 2; i <= n; i++) {
    
11.         if (isPrime[ i]) {
    
12.             primes.push_back(i);
    
13.             for (int j = i*2; j <= n; j += i) {
    
14.                 isPrime[j] = false;
    
15.             }
    
16.         }
    
17.     }
    
18. 
    
19.     return primes;
    
20. }
    
21. 
    
22. int main() {
    
23.     vector<int> primes = findPrimes(1000);
    
24. 
    
25.     for (int prime : primes) {
    
26.         cout << prime << " ";
    
27.     }
    
28.     cout << endl;
    
29. 
    
30.     return 0;
    
31. }
    

复制代码

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

跳转到最佳答案楼层

isdkz

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

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

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

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

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

1. #include <iostream>
   
2. #include <vector>
   
3. 
   
4. using namespace std;
   
5. 
   
6. vector<int> findPrimes(int n) {
   
7.     vector<bool> isPrime(n+1, true);
   
8.     vector<int> primes;
   
9. 
   
10.     for (int i = 2; i <= n; i++) {
    
11.         if (isPrime[ i]) {
    
12.             primes.push_back(i);
    
13.             for (int j = i*2; j <= n; j += i) {
    
14.                 isPrime[j] = false;
    
15.             }
    
16.         }
    
17.     }
    
18. 
    
19.     return primes;
    
20. }
    
21. 
    
22. int main() {
    
23.     vector<int> primes = findPrimes(1000);
    
24. 
    
25.     for (int prime : primes) {
    
26.         cout << prime << " ";
    
27.     }
    
28.     cout << endl;
    
29. 
    
30.     return 0;
    
31. }
    

复制代码

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

陈尚涵

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

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

难绷（