技术头条 - 一个快速在微博传播文章的方式     搜索本站
您现在的位置首页 --> 算法 --> 打印质数的各种算法

打印质数的各种算法

浏览:2523次  出处信息

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

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

        首先,先给一个教科书的示例。下面这个示例应该是教科书(至少是我上大学时的教科学)中算法复杂度最好的例子了。其想法很简单,先写一个判断是否是质数的函数isPrime(),然后从1到n分别调用isPrime()函数来检查。检查是否是质数的算法是核心,其简单的使用从2到n的开根的数作为除数。这样的算法复杂度几乎是O(n*log(n)),看上去不错,但其实很不经济。

    #include 
    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;
            }
        }
    }
    

    较好的算法

        我们知道,我们的算法如果写成线性算法,也就是O(n),已经算是不错了,但是最好的是O(Log(n))的算法,这是一个级数级的算法,著名的二分取中(Binary Search)正是O(Log(n))的算法。通常来说,O(Log(n))的算法都是以排除法做为手段的。所以,找质数的算法完全可以采用排除法的方式。如下所示,这种算法的复杂度是O(n(log(logn)))。

        示例:打印30以内的质数

        一、初始化如下列表。

     2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

        二、把第一个数(2)取出来,去掉所有可以被2整除的数。

     2  3     5     7     9    11    13    15    17    19    21    23    25    27    29

        三、取第二个数(3),去掉所有可以被 3整除的数。

     2  3     5     7          11    13          17    19          23    25          29

        四、取第三个数(5),因为4已经被去除了,再去掉所有可以被5整除的数。

     2  3     5     7          11    13          17    19          23                29

        接下来的数是7,但是7的平方是49,其大于了30,所以我们可以停止计算了。剩下的数就是所有的质数了。

    实际应用的算法

        实际应用中,我们通常不会使用上述的两种算法,因为那是理论学院派的算法。实际中的算法是,我把质数事先就计算好,放在一个文件中,然后在程序启动时(注意是在启动时读这个文件,而不是运行时每调用一次就读一次文件),读取这个文件,然后打印出来就可以了。如果需要查找的化,二分查找或是hash表查找将会获得巨大的性能提升。当然,这样的方法对于空间来说比前面两个都要消耗得大,但是你可以有O(log(n))或是O(1)的时间复杂度。

        所以,我想在这里提醒大家――实际和理论的的方法很不一样的,千万不要读书读成书呆子。在游戏编程的世界里,大量的数据都不是运行计算的,而都是写在文件中的。比如,一个火焰效果,一个人物跑动的动作,都是事先写在文件中的。

    使用编译时而不是运行时

        下面这个例子(本例参考于这里)你需要注意了,这是一个高级用法,使用模式来在编译时计算质数,而不是运行时。这种技术使用了C++编译器对模板的特化时的处理来生成自己相要的结果。这种方法在技术上是相当Cool的,但并不一定实用,这里只是想像大家展示这种用法。这是C++的最骨灰级的用法了。

        请看下面的两个模板类,第一个模板以递归的方式检查是否是质数,第二个方法是递归的退出条件(当N=1时),对于模板的重载,请参看相关的C++书籍。

    template
    struct isPrime {
        enum {
            result = (N % D) && isPrime::result
        };
    };
    
    template
    struct isPrime {
        enum {
            result = true
        };
    };
    

        于是,通过这个模板,我们可以使用下面的代码来检查是否是质数:

    if (isPrime<3>::result)
        cout << "Guess what: 3 is a prime!";
    

        下一步,我们需要打出一个区间内的质数,所以,我们需要继续设计我们的print模板。

    template
    struct printIfPrime {
        static inline void print() {}
    };
    
    template 
    struct printIfPrime {
        static inline void print() {
            std::cout << N << endl;
        }
    };
    

        从上面的代码中,我们可以看到,我们的第一个实际是什么也没做,而第二个有输出,注意第二个的模板参数中有一个true,其意味着那个质数的判断。于是我们就可以给出下面的代码来尝试着打印出一段区间内的质数:(请不要编译!!因为那会让编译器进入无限循环中,原因是printPrimes会不停地调用自己永不停止)

    template
    struct printPrimes {
        static inline void print()
        {
            printIfPrime::result>::print();
            printPrimes::print();
        }
    };
    

        为了避免这个问题,你需要再加一个模板类,如下所示。这样当N变成MAX的时候,递归就结束了。

    template
    struct printPrimes {
        static inline void print() {
            printIfPrime::result>::print();
        }
    };
    

        最后,让我们来看看最终的调用:

    int main (int argc, char * const argv[])
    {
        printPrimes<2, 40>::print();
        return 0;
    }
    

        这个方法很NB,但是有两个问题:

  • 比较耗编译时间。
  • 不能在运行时输入MAX的值。
  •     不过,相信这种玩法会启动你很多的编程思路。

        (全文完)

    建议继续学习:

    1. 用抛物线筛选质数    (阅读:3576)
    2. 用 JS 枚举质数    (阅读:1973)
    QQ技术交流群:445447336,欢迎加入!
    扫一扫订阅我的微信号:IT技术博客大学习
    © 2009 - 2024 by blogread.cn 微博:@IT技术博客大学习

    京ICP备15002552号-1