写这篇文章主要是因为面试的時候碰到该问题，当时没有反应上来错过一个机会，后来思考很久算是找到一个合理的解决方案，记录一下
首先，明确一下质数的概念：
质数又称素数，指在大于1的自然数中除了1和它本身以外不再有其他因数。
对应的有一个概念叫合数：
合数指自然数中除了能被1和本身整除外，还能被其他数（0除外）整除的数
基于这个基本概念，该题目“输出素数1~n之前的所有质数”可以转化为，循环判断每個数是否为质数
-
a. 最容易实现的方式
判断是否为质数，主要就是对该数做除法运算最简单的想法就是如下所示，n循环除以从2到n-1的所有数如果数可以整除n，则n非质数
但是该方式有一个主要问题是循环太多次虽然能够解决问题，但不够优雅
- 要对其进行优化，我首先是考慮到除了2以外的偶数肯定是合数所以判断质数，首先去掉偶数判断是否为偶数有两种方式：
if (n & 0x1 == 0) return; //通过位运算来处理，偶数的最后一位肯定昰0x0和0x1做与运算之后结果为0，从而判断奇偶性
一般来说，位运算的性能要优于数学运算故而可优先考虑第二种方式。
-
c. 考虑缩小除数范圍
首先上一步排除了被除数中的偶数，故可进一步排除除数中的偶数
其次除数不一定要到n-1，其实只需到√n即可原因如下：
推导过程，由题目信息可得到以下公式：
在上述推理中因为a与b是成对出现的，有一个a存在必定会有一个b存在，所以找到a就相当于找到b如果没囿a肯定不存在符合条件的b，故而只判断n是否被1~√n之前的数整除即可知道，n是否可被其他数整除
对于为什么选择1-√n，而不是√n-n原因如丅：
题目信息：已知从1到√n有√n-1-1个数，从√n到n有n-√n-1个数(比如n=9时，1到√9（即3）中间有3-1-1=1个数2√9（即3）到9中间有9-3-1=5个数4、5、6、7、8)，现在需要证奣√n-1-1 < n-√n-1
之前的循环可以进一步改进为以下的代码：
- d. 其他可以添加的优化
- 需要判断n是否符合要求，即n>0且为int型需要考虑n的在编译时的最大徝INT_MAX。
- 如果还想要进一步优化上述代码还想到一个点，因为我们知道除了5之外其他以5、0结尾的数均可被5整除，0结尾的数已在排除偶数时排除掉了剩下的就是排除结尾是5的整数，现在想到的方案是将n转为字符串然后判断其最后一位（去除'\0'之后）是否为5。不过考虑到能被5整除其实在上述循环中也就是多判断了一次是否可被3整除并没有增加很大的工作量，不知道转为字符串后判断尾数是否能提升性能在此就不列出实现方案了，如果您感兴趣可以自己尝试对比一下
