今天坐在桌前，在思考，以我这种小白的水平怎么去写一个自己的算法呢？ 于是我看到了一道题，一个求素数的题。 我想起来第一次的暴力破解，运用了很多循环，简而言之就是一个一个的循环下来，相比那个代码大家也非常的熟悉吧：
#include<stdio.h> int main(){ int i, j, key = 0; printf("2 "); for( i = 3; i < 100000; i++){ for(j = 2; j < i; j++){ if(i%j == 0){ key = 1; } } if(key == 0){ printf("%d ", i); } key = 0; } return 0; }我们用双层循环嵌套进行，其中，我们需要一个key作为“钥匙”来作为我们确定是否找到了素数的标志~如果key为0，则说明我们没有找到一个可以因数，那么这个i就是我们再找的素数 我们定义一个足够大的数来验证一下 我们所选的数为四十万 我的天，真的没想到会要这么久，七分多钟呢~
接下来就是分析问题了，为什么会耗时如此厉害？ 如何解决呢？
首先，我们可以肯定一点，所有的素数，除了2，就不再会有偶数的，对吧~ 那么我们是不是就意识到一个问题，我们其实不必要一个一个的加起来了？ 并且还有一个问题，我们也并不用在内部循环一直到i，因为一旦超过i/2以后，那么也就不用考虑了
#include<stdio.h> int main(){ int i, j, key = 0; printf("2 3 ");//加上3\n for( i = 5; i < 400000; i+=2){ //i从5开始，避开3%3=0的问题，i++改为 i+=2 for(j = 3; j < i/2; j+=2){ //j从3开始，因为已经排除了所有偶数 if(i%j == 0){ key = 1; } } if(key == 0){ printf("%d ", i); } key = 0; } return 0; }在这里，我们在内外都减少了一半的循环，大家可以想象，一般的循环次数是内圈乘以外圈，之前的四百多秒就是20乘以20，那么现在我们的改进后的应该就是10乘以10/2了吧，大概会在50秒左右了~ 看看结果~
结果很明确，还真的是五十多秒，真刺激~
但这还不是我们想要的，我们在看看代码的问题，一般学完分支语句后我们都会接触到一个指令break，一般用作跳出当前模块，对吧~ 那我们细想一下啊，在这个程序中，我们一般只用检测到一个因数，就可以说明当前的数不是质数了，对吧？ 于是乎，我们在其中套入一个break吧~
#include<stdio.h> int main(){ int i, j, key = 0; printf("2 3 "); for( i = 5; i < 400000; i+=2){ for(j = 3; j < i; j+=2){ if(i%j == 0){ key = 1; break; //加入break } } if(key == 0){ printf("%d ", i); } key = 0; } return 0; }break的插入迅速减少了内部循环的次数，而究竟多少次，这个我也无从知晓，应该会很快的
二十秒！ 一个break居然为我们减少了这么多的时间！！！ 真的很不可思议！ 那么到现在究竟还有什么方法可以继续为我们服务，来降低他的时间呢？
学C语言的小伙伴们应该清楚，C语言有着其他的函数库，这些函数库中就存在着一些非常有用的函数，今天我们需要用到的函数就是<math.h>这个头文件中的sqrt 他是一个开方用的函数~ 那么它可以用来干么呢？在这道题目中，我们还能用它优化哪呢？
举个例子：36的因数有哪些？ 2， 3， 4， 6， 9， 12， 18 我们可以发现其实找到6就足够了！因为超过6的数后面的数，其实是和6前面的数一对儿的！ 2和18 3和12 4和9
那么如果一个数只要检测到他的平方根的时候发现没有因数，那么后面也不会有了，所以它就是质数了！
#include<stdio.h> #include<math.h> int main(){ int i, j, key = 0; printf("2 3 "); for( i = 5; i < 400000; i+=2){ for(j = 3; j < sqrt(i); j+=2){ if(i%j == 0){ key = 1; break; } } if(key == 0){ printf("%d ", i); } key = 0; } return 0; }来瞧瞧运行结果？
3.667秒，真棒！ 事到如今，也就差不多了~ 才怪！
一直到这里，其实都还算不上算法！ 那么这道题是否还可以更加的简便？ 当然可以！
我们需要思考一个问题，质数是什么？能用来干什么？
举个例子，还是36，我们再来分解他~ 这一次我们分解的更加彻底！ 36 = 2233 2是质数么？3是质数么？ 换一个数试试122 112=2222*7 2和7依旧是质数 是的！ 所有的数分解以后都是由质数组成的！ 那么我们接下来只需要将内部循环的数全部改成质数就可以了！但别忘了，我们需要将质数全部储存起来，在这里我们只能牺牲空间换取时间了。于是我重新写了一遍代码，经行测试！
#include<stdio.h> int main(){ int i, j, t = 0, k[35000], key = 0; k[0] = 2; for(i = 3; i < 400000; i+=2){ j = 0; for(j = 0; j < t+1; j++){ if(i%k[j] == 0){ key++; break; } } if(key == 0){ t++; k[t] = i; } key = 0; } for(i = 0; i < t; i++){ printf("%d ", k[i]); } return 0; }真不错，我们再来运行一下吧 哇哦！3.188秒！ 虽然这并没有快多少，但却是也是略有进步，并且虽然牺牲了空间，但从计数和其他方面也存在一定的优势哦~ 好啦，今天就写到这里了~
