最近几个月，一直受到某位前辈的指导与引领。在他的推荐和建议，俺也渐渐认识到了开个博客来record自己在学习中的一些心得体会的重要性，于是申请开通博客也应运而生:D。（这里，也推荐大家去阅读一下大佬的关于为什么开博客的建议：[BetterExplained]为什么你应该（从现在开始就）写博客 – 刘未鹏 | Mind Hacks，这是一篇09年的文章，现在看依然很受启发，写博客一举多得，何乐而不为呢？

　　作为俺的第一篇博客文章，对于主题的选取，俺没有纠结多久。由于俺最近为了刷分选择了复修C语言:(,咱选择深度剖析那道经典C语言题及面试典例——求出100以内的所有素数。

　　一些小伙伴可能看到这个，就觉得太过简单就划走了。但俺一直认为，能将一件简单的事开发到极致也不失为一种乐趣，同时也在一定程度反映了你的代码基础水平和思考问题的深度，重要性不言而喻。so,就让我们一起看看这一道题，能翻出多少新花样来吧？

 

★Level 1 

　　最土的办法——试除法，几乎是新手才会使用。就是从2试到这个数减一未知，没有任何技术含量，不推荐使用。

 

★Level 2

　　较之1稍强一些，就是从2试到这个数的一半，工作量少一半，但依然不推荐。

 

★Level 3

　　有些小伙伴可能稍稍思索了一下，会发现，除了2以外，所有可能的质因数都是奇数。所以，他们就先尝试 2，然后再尝试从 3 开始一直到 x/2 的所有奇数。工作量又少了一半，仍然不推荐。

 

★Level 4

　　这是国内一些教材上列举出了的方法，即从2试到这个数的开平方。原理就是很基本的数学因子分解的规律，如100=10*10=4*25*1*100=2*50=....，可以观察出，100的两个因子，必有一个小于100的开方，一个大于等于100的开方。故我们试除的时候，只需试到这个数的开方取整即可。

#include<stdio.h>
#include<math.h>
int isPrime(int a){
    int i=0;
    for (i = 2; i <= sqrt(a);i++){
        if(0==a%i){
            return 0;
        }
    }
    return 1;
}
int main(){
    int arr[100];
    for (int i = 0; i < 100;i++){
        arr[i] = i + 2;
        if(isPrime(arr[i]))
            printf("%d\n", arr[i]);
    }
    return 0;
}

 

★Level 5

　　在这里，有些聪明的小伙伴可能会提出，可不可以同时利用Level 3和Level 4呢，就是从3取到这个数的开方，并只取其中的奇数，这不就是再提高一层了吗？我的回答是可以，但还不够:P

　　我们提出一个数101作作分析，可以看到，我们首先对101开方并取整，得到10，然后依次取3，5，7，9进行试除，但是仔细观察，我们便发现9的试除是没有必要，因为9是3的倍数，3如果无法整除，那么9也必然无法整除，因此，我们只要尝试小于√ x 的 质数即可。而这些质数，恰好前面已经算出来了（是不是觉得很妙？）。

　　所以聪明的小伙伴，再每次求出一个质数时会将它保存起来，再下一次的试除中再利用，这大大提高了效率。

 

★Level 6

　　接下来，俺就要介绍今天的主角，埃拉托斯特尼筛法，也称素数筛。它的原理极其巧妙，通俗易懂，且具有普适性。

　　具体操作步骤是：第一步：把目前没有被删除的数中第一个数（最小的数）画圈，然后把这个画圈的数后面所有这个数的倍数删除，这步中画圈的数就是2，被删除的数就是4，6，8，...... 。第二步：与第一步的操作方式类似，具体来说就是把目前没有画圈也没有被删除的数中的最小的一个数即3画圈，再把比3大的3的倍数删除，即删除，9，15，...... （注意，3的倍数中有的也是2的倍数，比如6,12等等，之前已经被删除过了。这样一直做下去，一定可以把所有100以内的素数全部找出来。）

• 　　我从维基上找到的一张动图非常形象地直观地体现了筛法的工作原理：

 

 剖出代码如下：

#define N 100 
#include "stdio.h"
int main(){
    int i,j;
    int arr[N];
 
    for(i = 0;i<N;i++)
    {
        arr[i]=i+1;
    }
    arr[0] = 0;//1不是素数，所以将下标0 的元素设置为0
    
    //进行素数判断
    for(i = 1;i < N-1;i++){
        for(j = i+1;j < N;j++){
            if(arr[i] != 0 && arr[j] != 0)//如果进行到3的时候2后面一定有数被置为0了，这里我们需要判断一下是不是有0
            if(arr[j] % arr[i] == 0){
                arr[j] = 0;
            }
        }
    }
    //循环输出
    int cnt = 0;
    for(i = 0;i<N;i++)
    {
        if(arr[i] != 0)
        {
            printf("%d\n",arr[i]);
            cnt++;
        }
    }
    return 0;
}

 

 提升容器的不同境界：

stadge 1:

　　咱先说说最土的搞法（新手时期）——直接构造一个整型的容器。在筛的过程中把发现的合数删除掉，最后容器中就只剩下质数了。

那么，为什么咱都不推荐这种方法捏？？

　　首先，整型的容器，浪费内存空间。比方说，你用的是32位的C/C++或者是Java，那么每个 int 都至少用掉4个字节的内存。当 N 很大时，内存开销就成问题了。

　　其次，当 N 很大时，频繁地对一个大的容器进行删除操作可能会导致频繁的内存分配和释放（具体取决于容器的实现方式）；而频繁的内存分配/释放，会导致明显的CPU占用并可能造成内存碎片。

　　最后，太朴素没有深度，不能装逼。

 

stadge 2

　　为了避免境界1导致的弊端，更聪明的小伙伴们会构造一个定长的布尔型容器（通常用数组）。比方说，质数的分布范围是1,000,000，那么就构造一个包含1,000,000个布尔值的数组。然后把所有元素都初始化为 true。在筛的过程中，一旦发现某个自然数是合数，就以该自然数为下标，把对应的布尔值改为 false。
　　全部筛完之后，遍历数组，找到那些值为 true 的元素，把他们的下标打印出来即可。
　　此种境界的好处在于：其一，由于容器是定长的，运算过程中避免了频繁的内存分配/释放；其二，在某些语言中，布尔型占用的空间比整型要小。比如C++的 bool 仅用1字节。

 

stadge 3
　　虽然境界2解决了境界1的弊端，但还是有很大的优化空间。有些程序猿会想出按位（bit）存储的思路。这其实是在境界2的基础上，优化了空间性能。俺觉得：C/C++出身的或者是玩过汇编语言的，比较容易往这方面想。
　　以C++为例。一个bool占用1字节内存。而1个字节有8个比特，每个比特可以表示0或1。所以，当你使用按位存储的方式，一个字节可以拿来当8个布尔型使用。所以，达到此境界的程序猿，会构造一个定长的byte数组，数组的每个byte存储8个布尔值。空间性能相比境界2，提高8倍（对于C++而言）。如果某种语言使用4字节表示布尔型，那么境界3比境界2，空间利用率提高32倍。

小结

童鞋们，看到这里，可能会在心中长舒一口气：终于结束了！

但是！俺想告诉大家的是，永远不要把局限自己的眼光，也不要束缚住自己滴思想。要知道，山外有山、天外有天。每一个技术领域里面的每一个细小的分支，深究下去都有很多的门道与奥妙。在你深究的过程中，必然会学到很多东西。深究的过程也就是你能力提高的过程。