【算法】判断一个数是否为素数的思想迭代与算法优化-C语言
判断一个数是否为素数
素数概念：素数就是质数，一个大于1的自然数，除了1和它自身外，不能整除其他自然数的数叫做质数，即素数
一、普通方法
-
思路：在了解了素数的概念后，我们就能根据概念设计一个排除的方法。因为素数是>1，且除了1和它自身外，不能整除其它自然数的数。那我们在判断一个数是否为素数的时候，便可以从2开始循环，然后利用if语句，如果某个数能够整除（除了1和它自身外）的其它自然数，即不是素数。为此我们需要用到for和if语句。
-
代码实现：
void isPrime(int x)
{
int ret = 1; // 素数标记
int i;
if( x == 1)
ret = 0; // 非素数标记
for( i=2; i-
缺点：需要遍历的次数太多了，时间复杂度太高了，效率低
-
时间复杂度：O(n)
二、优化-去掉偶数
-
优化点：偶数都是能被其它自然数整除的，那么在普通方法的基础上，将偶数给排除掉，只循环遍历奇数，那么遍历的次数将是n/2，效率提高了。
-
思路：去掉偶数，从3开始遍历起奇数
-
代码实现：
void isPrime(int x)
{
int ret = 1; // 素数标记
int i;
if( x == 1 || ( x % 2 == 0 && x != 2 )) // 排除掉除2以外的偶数
ret = 0; // 非素数标记
for( i=3; i-
缺点：尽管已经将复杂度变为一半，但仍不是最优的方案。
-
时间复杂度：O(n/2)
三、再度优化-sqrt(x)-循环至开平方根即可
-
优化点：以上普通方法和优化方法都是根据遍历多次才能确认一个数是不是素数。是否能根据素数的特点运用数学来设计更加优化的算法呢？还真有，那就是将x进行开平方。比如原本需要循环100次，现在只需要10次即可判断出来，算法效率大大提高。
-
原理：
-
简单版本：因为如果它不是质数，那么它一定可以表示成两个数（除了1和它本身）相乘，这两个数必然有一个小于等于它的平方根。只要找到小于或等于的那个就行了
-
证明版本： 假设数m=p * q，且p≤q。则m=p * q ≥ p * p。即p ≤ √m。所以m必有一个小于或等于其平方根的因数,那么验证素数时就只需要验证到其平方根就可以——这个证明通过数学的方式，证明了其中一个因数的取值范围是<=√m的。
-
举例版本： 首先举个例子，n = 100，开平方为10。100的每对儿因子，必定一个小于10，一个大于10。如：2和50，5和20，1和100等。因此，我们只需判断1-10中是否有100的因子。如果没有，那么大于10的数中，也不会有100的因子。推广到所有数中，可得结论：若要判断x是否为素数， 只需判断1~√x中是否有它的因子即可。
-
思路：排除掉偶数，然后从3开始遍历到√x的一个根。
-
代码实现：
void isPrime(int x)
{
int ret = 1; // 素数标记
int i;
if( x==1 || (x % 2 == 0 && x != 2 )) // 排除偶数
ret = 0;
for( i=3; i- 时间复杂度：O(√n)