判断一个数是否为素数?

最直观的方法判断。

根据定义，因为素数除了1和本身之外没有其他约数，所以判断n是否为素数，根据定义直接判断从2到n-1的数中有没有N的约数？如果找不到这样的约数，那么这个数就是素数，否则就不是素数。

首先是看这个数是否是大于1的自然数，然后看它除了1和这个数字本身之外还有没有其他的因数，比如13，只有1和13两个因数，所以是素数，10有1和10，2和5四个因数，所以它不是素数。

含义

如果为合数，因为任何一个合数都可以分解为几个素数的积；而N和N+1的最大公约数是1，所以不可能被p1，p2，pn整除，所以该合数分解得到的素因数肯定不在假设的素数集合中。因此无论该数是素数还是合数，都意味着在假设的有限个素数之外还存在着其他素数。所以原先的假设不成立。也就是说，素数有无穷多个。

最直观的方法，根据定义，因为素数除了1和本身之外没有其他约数，所以判断n是否为素数，根据定义直接判断从2到n-1的数中有没有N的约数？如果找不到这样的约数，那么这个数就是素数，否则就不是素数。

判断素数的方法首先是看这个数是否是大于1的自然数，然后看它除了1和这个数字本身之外还有没有其他的因数，比如13，只有1和13两个因数，所以是素数，10有1和10，2和5四个因数，所以它不是素数。

素数又称质数，所谓素数是指除了 1 和它本身以外，不能被任何整数整除的数，例如17就是素数，因为它不能被 2~16 的任一整数整除。

思路1、判断一个整数m是否是素数，只需把 m 被 2 ~ m-1 之间的每一个整数去除，如果都不能被整除，那么 m 就是一个素数。
思路2、判断方法还可以简化。

m 不必被2~m-1之间的每一个整数去除，只需被2~√m之间的每一个整数去除就可以了。如果 m 不能被2~√m 间任一整数整除，m必定是素数。例如判别17是是否为素数，只需使17被2~4之间的每一个整数去除，由于都不能整除，可以判定17是素数。

原因：因为如果m能被2~m-1之间任一整数整除，其二个因子必定有一个小于或等于√m，另一个大于或等于√m。

例如16能被2、4、8整除，16=28，2小于 4，8大于4，16=44，4=√16，因此只需判定在2~4之间有无因子即可。

两种思路的代码请看解析。

：

素数（prime number）又称质数，有无限个。素数定义为在大于1的自然数中，除了1和它本身以外不再有其他因数。

C语言是一门面向过程、抽象化的通用程序设计语言，广泛应用于底层开发。C语言能以简易的方式编译、处理低级存储器。C语言是仅产生少量的机器语言以及不需要任何运行环境支持便能运行的高效率程序设计语言。

参考资料：

百度百科——素数

百度百科——C语言

对于素数这个概念，我们自然会想到这样一个问题：怎样从自然数集合中找出素数？素数到底有多少个？
假设给定一个自然数N，要求出N以内的所有素数，可以这样进行：因为N以内的自然数只有三种，一种是1，一种是合数，一种是素数；我们可以象筛东西那样，先把1筛掉，然后再把合数筛掉，剩下的就是素数了，这种在自然数列中寻找素数的方法就叫做埃拉托色尼筛法(简称埃氏筛法)。
用筛法找出不超过N的全部素数，可以遵循下面的定理进行。
辅助定理1：“如果n是不大于x的合数，那么n必有一个不大于√x的素约数(符号“√”表示开平方)”(证从略)。根据辅助定理1，我们只要用不大于√x的素数作筛子，就可将不大于X以内的所有的合数筛除掉。
辅助定理2：“素数有无限多个”(证从略)。
虽然素数有无穷多个，但在自然数列中的一个相当长的数列中，却找不到一个素数，而有时会出现若p是素数，p+2也是素数的情况，所以素数的出现并无规则可言。
一个素数只有1和本身这两个约数，因此素数就不能再分解了。但是合数却有两个以上的素约数，那么合数能不能分解成约数全部是素数的乘积呢？答案是肯定的。
唯一分解定理：“任何大于1的自然数都可以分解成素数的乘积，如果不计较这些素因数的顺序，这种分解方法是唯一的”(证从略)。
根据唯一分解定理，欲求某自然数的倍数之数列，只要用该数乘以自然数列，即可得到该数的倍数之数列。由此可知，合数的出现是有规则可言的。埃氏筛法就是根据合数的出现是有规则可言的基础上，逐个地将不大于√x的素数的倍数筛掉。根据辅助定理1，可知，筛掉那些具有不大于√x素约数的合数，序列中已无合数的存在，剩下的就是大于√x至x的素数了。
在运用筛法时，就可发现，当筛除某数的倍数时，有时会遇到数列中的数已被前一个筛子所筛，这样就会造成计算上的误差。针对此种情况，在数论有一个逐步淘汰原则：
“设有N件事物，其中，N_i件有性质i，N_j件有性质j, , N_ij件兼有性质i及j，，N_ijk件兼有性质i、j及k，。则此事物中之既无性质i，又无性质j，又无性质k，者之件数为
N-N_i-N_j-N_k-+N_ij+-N_ijk-+-。”①。
根据埃氏筛法和逐步淘汰原则，数论创建了求不大于X以内的素数之函数π(x)。所谓的π(x)函数，是指：
π(x)=N-r-1-{r∑i=1}[N/pi]+{∑1≤iipj]-
+(-1)r[N/pipjpr]
这是数论中求自然数列中素数的个数问题之唯一的一个根据规律而创建的函数，而所谓的素数定理中的Lix(x)函数仅是由于计算出来的数值有接近于π(x)函数中的数值而被高斯先生提议替代π(x)函数之用。因为在π(x)函数中的取整之步骤，使得计算成为十分繁琐之事。但在Lix(x)函数中，并无所求素数的个数之任何规律，在Lix函数中，仅是对数函数的积分，而对数函数只是指数函数的反函数也。

1、查表法：
主要是指查“质数表”。编制质数表的过程是：按照自然数列，第一个数1不是质数，因此要除外，然后按顺序写出2至100的所有自然数，这些数中2是质数，把它留下，把2后面所有2的倍数划去，2后面的3是质数，接着再把3后面所有3的倍数划去，如此继续下去，剩下的便是100以内的全部质数。
2、试除法：
在手头上没有质数表的情况下，可以用试除法来判断一个自然数是不是质数。例如判断143、179是不是质数，就可以按从小到大的顺序用2、3、5、7、11……等质数去试除。一般情况下用20以内的2、3、5、7、11、13、17、19这8个质数去除就可以了。
如143，这个数的个位是3，排除了被2、5整除的可能性，它各位数字的和是1+4+3=8，也不可能被3整除，通过口算也证明不能被7整除，当试除到11时，商正好是13，到此就可以断定143不是质数。

---