用另一种C++的思路写一遍代码
时间: 2024-02-13 22:05:22 浏览: 70
好的,以下是使用线性筛法来找出10000以内的所有质数的C++代码:
```c++
#include <iostream>
#include <vector>
using namespace std;
int main()
{
int n = 10000;
vector<int> primes;
bool isComposite[n+1] = {false};
for(int i=2; i<=n; i++)
{
if(!isComposite[i])
primes.push_back(i);
for(int j=0; j<primes.size() && i*primes[j]<=n; j++)
{
isComposite[i*primes[j]] = true;
if(i % primes[j] == 0)
break;
}
}
for(int i=0; i<primes.size(); i++)
cout << primes[i] << " ";
return 0;
}
```
这个代码使用了线性筛法来找出10000以内的所有质数。具体来说,我们定义了一个vector类型的数组primes,用来存储找到的质数。然后,我们定义了一个bool类型的数组isComposite,其中isComposite[i]表示i是否为合数。初始时,将isComposite数组中所有元素都赋值为false。
接下来,我们从2开始循环,如果i是质数,则将i加入primes数组中。然后,我们遍历primes数组中的所有元素primes[j],如果i*primes[j]大于n,则跳出循环。否则,将i*primes[j]标记为合数,同时判断i是否可以整除primes[j],如果可以,则跳出循环。
最后,输出primes数组中的所有元素,即为10000以内的所有质数。
相对于埃拉托斯特尼筛法,线性筛法更加高效,时间复杂度为O(n)。
阅读全文