定义介绍如何求素数之前，首先得明白素数是什么？所谓素数（也叫质数），是指大于1，且只能被1和其本身整除的数（此定义与合数的定义相对）。
简便求法在对时间复杂度没有要求的情况下，直接从定义出发，利用循环，一直做取余运算，就可以很容易的得到判断一个数字是否为素数的算法，具体如下：
123456789101112131415bool Is_Prime(int number) { bool flag = true; int i; if(number <= 1) { flag = false; } else { for(i = 2; i < number; i++) { if(number % i == 0) { flag = false; break; } } } return flag;}
很明显，因为借助了一层循环，所以时间复杂度$O(n)$，优点就是十分容易理解了。
结合数学知识的优化在理解了简便求法之后，来稍微思考一下，偶数能被2整除，所以肯定不是素数，如果一开始先判断number是不是偶数，然后在从 3 开始判断number是否能被奇数整除，如此一来，整个循环次数就是$(n - 3) / 2 + 1$（奇数每次增加2，所以分母为2）了，当$n$较大的时候，这个值是趋近于$n / 2$的。接着来改写一下代码：
123456789101112131415bool Is_Prime(int number) { bool flag = true; int i; if(number <= 1 || (number % 2 == 0 && number != 2)) { flag = false; } else { for(i = 3; i < number; i += 2) { if(number % i == 0) { flag = false; break; } } } return flag;}
相比简便求法，将总体时间缩短了一半，时间复杂度是$O(n/2)$。
实际上，循环区间可以缩减为$[3, \sqrt{number})$（此处的数学证明就不多说了😁，可以简单想一下，一个数$n$，对于$x <= n$，如果$n$能整除$x$，则$n$也一定能整除$n/x$，这两个数中必定有一个大于等于$\sqrt{n}$），具体如下：
123456789101112131415bool Is_Prime(int number) { bool flag = true; int i; if(number <= 1 || (number % 2 == 0 && number != 2)) { flag = false; } else { for(i = 3; i * i < number; i += 2) { if(number % i == 0) { flag = false; break; } } } return flag;}
上述代码块中用i * i来代表平方根的写法较为常见，这样此算法的时间复杂度就为$O(\sqrt{n})$。但是，i * i这种写法，会溢出，最好就使用sqrt函数。
转换思路按照之前的做法，无论i的值是素数还是合数，都对number进行了整除的运算。实际上，判断number是否为素数，只需要在i的值为素数的情况下，判断number是否能被i整除即可，若能整除则不是素数，反之则是。在进行上述计算的过程中，需要提前准备一张素数表来帮助计算，具体如下：
1234567891011bool Is_Prime(int number, int Prime[], int NumOfPrime) { bool flag = true; int i; for(i = 0; i < NumOfPrime; i++) { if(a % Prime[i] == 0) { flag = false; break; } } return flag;}
在计算的数据较大的情况下，无法直接给定素数表，需要边判断边更新，这样会消耗掉一定的时间，所以上述算法的实际时间复杂度$O(n) ∈ (\sqrt{n}, n/2)$，但此法很适合需要构造素数表并求和的场景。
紧接着刚才的思路，以2为例，在判断出其为素数后，其倍数$4、6、8、10...$就是非素数了，那么一次性将这些数字标记为非素数，也可以提高效率，这就是“筛选法”构造素数表，具体如下：
1234567891011121314bool IsPrime[NumOfPrime];for(i = 2; i < NumOfPrime; i++) { IsPrime[NumOfPrime] = 1;}void Get_Prime() { int x, i; for(x = 2; x < MaxNum; x++) { if( IsPrime[x] ) { for(i = 2; i * x < MaxNum; i++) { IsPrime[i*x] = 0; } } }}
粗略分析代码，可知此算法时间的复杂度为$O(n * loglog{n})$，之所以是这个时间复杂度，是因为一次性计算出了$[0, MaxNum)$这个区间内的所有素数，此算法实际效果较好，对于需要构造素数表的情况很方便。
扩展上面介绍的“筛选法”，其实是古希腊数学家埃拉托色尼（Eratosthenes，274 B.C ~ 194 B.C）提出的一种筛选法，也称埃氏筛法。实际上，结合利用素数表来判断素数的思路，对于合数而言，如果其只要被其最小质因子整除，即可判断其不是素数。那么去掉这部分重复计算的过程，不就可以提高效率了吗？以16为例，在埃氏筛法中，$x = 2$时，筛选掉了$4、6、8、10...$，当$x = 3$时，又重复计算了$6、12...$等数。接着来修改下代码：
123456789101112bool Number[MaxNum];memset(Number, true, sizeof(Number));int Prime[MaxNum], count = 0;for(i = 2; i < MaxNum; i++) { if( Number[i] ) { Prime[count++] = i; for(j = 1; j <= num && i * Prime[j] <= n; j++) { Number[i * Prime[j]] = false; if(i % Prime[j] == 0) break; } }}
上述代码的时间复杂度为$O(n)$（计算过程暂不深究），所以此种筛法也叫线性筛法，不过提升效率的代价就是多余的空间开销了，一般而言的优化都是用空间换时间这样的思路。
