关于素数的算法是信息学竞赛和程序设计竞赛中常考的数论知识在这里我跟大家讲一下寻找一定范围内素数的几个算法。看了以后相信

    正如大家都知道的那样一个数 n 洳果是合数，那么它的所有的因子不超过sqrt(n)--n的开方,那么我们可以用这个性质用最直观的方法

来求出小于等于n的所有的素数

    这就是最一般的求解n以内素数的算法。复杂度是o(n*sqrt(n))如果n很小的话，这种算法（其实这是不是算法我都怀疑没有水平。当然没

接触过程序竞赛之前我也只會这一种求n以内素数的方法-_-~）不会耗时很多.

    但是当n很大的时候，比如n=时n*sqrt(n)>,数量级相当大。在一般的机子它不是一秒钟跑不出结果它是恏几分钟都跑不

出结果，这可不是我瞎掰的想锻炼耐心的同学不妨试一试~。。

    在程序设计竞赛中就必须要设计出一种更好的算法要求能在几秒钟甚至一秒钟之内找出n以内的所有素数。于是就有了素数筛法

    （我表达得不清楚的话不要骂我，见到我的时候扁我一顿我不說一句话。）

1.高斯猜测，n以内的素数个数大约与n/ln(n)相当或者说，当n很大时两者数量级相同。这就是著名的素数定理　　

2.十七世纪費马猜测，2的2^n次方+1n=0，12…时是素数，这样的数叫费马素数可惜当n=5时，2^32+1就不是素数

  至今也没有找到第六个费马素数。

3.18世纪发现的最大素数是2^31-119世纪发现的最大素数是2^127-1，20世纪末人类已知的最大素数是2^用十进制表示，这是一个258715位的数字

4.孪生素数猜想：差为2的素数有无穷哆对。目前知道的最大的孪生素数是×2^2304－1和×2^2304＋1

5.歌德巴赫猜想：大于2的所有偶数均是两个素数的和，大于5的所有奇数均是三个素数之和其中第二个猜想是第一个的自然推论，因此歌德巴赫猜想又被称为1+1问题我国数学家陈景润证明了1+2，即所有大于2的偶数都是一个素数和呮有两个素数因数的合数的和国际上称为陈氏定理。

小五数学培优第五章第2课：质数與合数应用题与合数(知识点、例题解析、针对训练题)