打印质数的各种算法

打印质数的各种算法

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

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

教科书的示例

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

较好的算法

我们知道,我们的算法如果写成线性算法,也就是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<int N, int D = N - 1>
struct isPrime {
    enum {
        result = (N % D) && isPrime<N, D-1>::result
    };
};

template<int N>
struct isPrime<N, 1> {
    enum {
        result = true
    };
};

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

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

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

template<int N, bool ISPRIME>
struct printIfPrime {
    static inline void print() {}
};

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

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

template<int N, int MAX>
struct printPrimes {
    static inline void print()
    {
        printIfPrime<N, isPrime<N>::result>::print();
        printPrimes<N + 1, MAX>::print();
    }
};

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

template<int N>
struct printPrimes<N, N> {
    static inline void print() {
        printIfPrime<N, isPrime<N>::result>::print();
    }
};

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

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

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

  • 比较耗编译时间。
  • 不能在运行时输入MAX的值。

不过,相信这种玩法会启动你很多的编程思路。

当然,还有以前说过的那个——《检查素数的正则表达式

(全文完)

(转载本站文章请注明作者和出处 酷 壳 – CoolShell ,请勿用于任何商业用途)

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

打印质数的各种算法》的相关评论

  1. 很好的文章,特别是第二个算法,很实际。第三个很Geeker。

    另外,教科书实例中循环 for (int d = 2; (d * d) <= (nr + 1); ++d)
    似乎循环到 (d * d) <= nr; 就可以结束了,为什麽要到nr + 1呢?

  2. 存文件和运行时计算是要权衡的,有时候数据大到蛋疼,但生成算法很简单,那即便生成比较费时,也只能认了。

  3. @WindyWinter
    nr=3的时候,也没什么问题啊。
    如果nr不是质数,必然有两个大于1的正整数(质因数),使得p*q=nr, 进一步得出p和q中必须有一个位于区间[2, 根号(nr)]上,因此只需循环到 (d * d) <= nr 就可以断定是否存在这样的质因数。

  4. 第一个算法是O(sqrt(n))的吧,怎么会接近O(nlog(n))呢?如果是O(nlog(n))的,那RSA就不安全了

  5. @digiter
    给个O(n)筛素数的方法:

    const int size = 1000 * 1000 + 5;
    bool isp[size];
    int prime[size], lp;
    void make() {
    	memset(isp, true, sizeof(isp));
    	isp[0] = isp[1] = false;
    	lp = 0;
    	for (int i = 2; i < size; ++i) {
    		if (isp[i]) {
    			prime[lp++] = i;
    		}
    		for (int j = 0; j < lp && (long long)i * prime[j] < size; ++j) {
    			isp[i * prime[j]] = false;
    			if (i % prime[j] == 0) {
    				break;
    			}
    		}	
    	}
    }
    
  6. tinybit :
    很好的文章,特别是第二个算法,很实际。第三个很Geeker。
    另外,教科书实例中循环 for (int d = 2; (d * d) <= (nr + 1); ++d)
    似乎循环到 (d * d) <= nr; 就可以结束了,为什麽要到nr + 1呢?

    有的版本是先算出sqrt(n),但是这样会有精度损失,为了以防万一会故意另i<sqrt(i+1.0)时循环终止,我想这个+1的风格可能是这样延续下来的。。

  7. 较好的算法,那一节第二行,有个错误:写成”级数级的算法”了,应该是对数级的算法log(n)

  8. 所以,我想在这里提醒大家——实际和理论的的方法很不一样的,千万不要读书读成书呆子。在游戏编程的世界里,大量的数据都不是运行计算的,而都是写在文件中的。比如,一个火焰效果,一个人物跑动的动作,都是事先写在文件中的。
    ————————
    这一段有点小问题,为了追求真实度,现在的游戏特效也大部分是用gpu实时演算的,像光影,爆炸,碰撞,等等。 纯挑刺纯挑刺~哈哈~

  9. 第一种方法求单个是否是素数时间复杂度是O(sqrt(n))而0-n是O(n*sqrt(n) 第二种均摊o(n)但是其直接求出0-N所有的素数 但是其最大的问题是需要开辟额外的内存 面对大素数鸭梨很大 另外有2种介于第一种和第二种直接的求素数的方式费马测试 和 米勒测试 比较犀利

  10. @tinybit
    根据质数的定义,在判断一个数N是否是质数时,我们只要用1至N – 1去除N,看看能否整除即可。但我们有更好的办法。先找一个数M,使M的平方大于N,再用 <= M的质数去除N(N即为被除数),如果都不能整除,则N必然是质数。

  11. tinybit :
    很好的文章,特别是第二个算法,很实际。第三个很Geeker。
    另外,教科书实例中循环 for (int d = 2; (d * d) <= (nr + 1); ++d)
    似乎循环到 (d * d) <= nr; 就可以结束了,为什麽要到nr + 1呢?

    @tinybit <nr+1和<=nr不是一样吗

  12. 虽然 1 既不是质数也不是合数, 但是我还是写错了, 写了printPrime 会由于
    isPrime 而导致编译死循环( -1 被解释为 unsigned int, 由于各编译器嵌套深度上线不一样, 所以所得的值也不一样), 我尝试在 enum 中加入 ?: 表达式, 未果, 修改方法如下:
    template
    struct isPrime
    {
    enum {result = 2 < N ?
    N % D && isPrime::result : false} ;
    } ;
    请问楼主有什么好方法能防止上述情况?

  13. 这里讨论的是最基本的trial division法,更大的质数用这种方法效率就很低了,看了下wiki上质数的段落,检测大质数的算法真麻烦,需要有很好的数学功底。

  14. 我们发现在2,3,5,7这4个数了没有如果一个数是素数肯定是2,3,5,7这几个数组成的。

  15. “较好的算法”实际上还有提高空间,可以用一个素数列表保存已筛选出的素数,对后面的每个数n,使用 <= sqrt(n) 的素数筛选,这样算法复杂度不变,空间占用从 O(N) 降到了 O(N/lnN)。

  16. digiter :
    @digiter
    给个O(n)筛素数的方法:
    12345678910111213141516171819const int size = 1000 * 1000 + 5;bool isp[size];int prime[size], lp;void make() {    memset(isp, true, sizeof(isp));    isp[0] = isp[1] = false;    lp = 0;    for (int i = 2; i < size; ++i) {        if (isp[i]) {            prime[lp++] = i;        }        for (int j = 0; j < lp && (long long)i * prime[j] < size; ++j) {            isp[i * prime[j]] = false;            if (i % prime[j] == 0) {                break;            }        }       }}

    镶嵌for难道不是O(n^2)吗?反正我想不出来怎么可能是O(n)

  17. 我觉得isPrime中的result按照惯用应该改成value,最后的那个模板特化中的N改成MAX应该更好理解,毕竟编译的递归是在N+1=MAX时停止的。

  18. 而且isPrime没有处理N=1的情况,如果N=1,那么D=0,所以应该再加个模板特化
    template
    struct is_prime
    {
    enum{value = false};
    };
    template
    struct is_prime
    {
    enum{value = false};
    };

    同理,对于N为负数的情况,也没有做太多处理,所以isPrime的N的类型应该改为size_t

  19. 那个模板的方法,只能在编译时求解有限个数的质数,因为编译器对模板的递归调用是有限制的,比如clang++的,fatal error: recursive template instantiation exceeded maximum depth of 256

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注