打印质数的各种算法
打印质数的算法应该是学习计算机编程的一个经典的问题，在这里想给大家展示一些方法，相信这些方法会对你的编程有一定的启发作用。请你注意几点，
- 实际应用和教学应用有很大的差别。
- 最后的那个使用编译时而不是运行时的方法大家可以重点看看。
教科书的示例
首先，先给一个教科书的示例。下面这个示例应该是教科书（至少是我上大学时的教科学）中算法复杂度最好的例子了。其想法很简单，先写一个判断是否是质数的函数isPrime()，然后从1到n分别调用isPrime()函数来检查。检查是否是质数的算法是核心，其简单的使用从2到n的开根的数作为除数。这样的算法复杂度几乎是O(n*log(n))，看上去不错，但其实很不经济。
#include <iostream>
using namespace std;
bool isPrime(int nr)
{
for (int d = 2; (d * d) < (nr + 1); ++d){
if (!(nr % d)){
return false;
}
}
return true;
}
int main (int argc, char * const argv[])
{
for (int i = 0; i < 50; ++i){
if (isPrime(i)){
cout << i << endl;
}
}
}
…
(14 人打了分，平均分： 3.14 )
Loading...
