Browsed by
标签:Template

打印质数的各种算法

打印质数的各种算法

打印质数的算法应该是学习计算机编程的一个经典的问题,在这里想给大家展示一些方法,相信这些方法会对你的编程有一定的启发作用。请你注意几点,

  • 实际应用和教学应用有很大的差别。
  • 最后的那个使用编译时而不是运行时的方法大家可以重点看看。

教科书的示例

首先,先给一个教科书的示例。下面这个示例应该是教科书(至少是我上大学时的教科学)中算法复杂度最好的例子了。其想法很简单,先写一个判断是否是质数的函数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;
        }
    }
}

阅读全文 Read More

好烂啊有点差凑合看看还不错很精彩 (10 人打了分,平均分: 4.00 )
Loading...