我目前正在读“编程:原理与实践使用C++”,在第4章存在这样的练习:埃拉托色尼算法的筛
我需要一个程序来计算素数字介于1到100之间,使用Eratosthenes算法筛选。
这是我想出了程序:
#include <vector>
#include <iostream>
using namespace std;
//finds prime numbers using Sieve of Eratosthenes algorithm
vector<int> calc_primes(const int max);
int main()
{
const int max = 100;
vector<int> primes = calc_primes(max);
for(int i = 0; i < primes.size(); i++)
{
if(primes[i] != 0)
cout<<primes[i]<<endl;
}
return 0;
}
vector<int> calc_primes(const int max)
{
vector<int> primes;
for(int i = 2; i < max; i++)
{
primes.push_back(i);
}
for(int i = 0; i < primes.size(); i++)
{
if(!(primes[i] % 2) && primes[i] != 2)
primes[i] = 0;
else if(!(primes[i] % 3) && primes[i] != 3)
primes[i]= 0;
else if(!(primes[i] % 5) && primes[i] != 5)
primes[i]= 0;
else if(!(primes[i] % 7) && primes[i] != 7)
primes[i]= 0;
}
return primes;
}
没有最好或最快的,但我在书中还早,不知道很多关于C++。
现在的问题,直到max
不大于500
所有打印在控制台上的值,如果max > 500
不是所有的打印。
我做错了什么?
P.S .:还有任何建设性的批评将不胜感激。
这不是Eratosthenes算法的筛选。你似乎只筛选可以被2,3,5和7整除的值,但是可以被其他素数整除的值呢?提示:你根本不需要模数。 http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes – UncleBens 2009-12-23 19:37:09
可否请您提供一个开箱即用的编译示例? – 2009-12-23 19:42:22
肯定对不起我的坏 – RaouL 2009-12-23 19:44:58