素数定义为在大于1的自然数中，除了1和它本身以外不再有其他因数。 ## 按照定义计算 由素数的定义可知，我们只要判断从2~n-1是否有它的因子即可判断这个数是否是素数： int n,i; for(i=2;i<n;i++){ if(n%i==0){ break; } } if(i==n) printf("%d is a prime\n"); else printf("%d isn't a prime\n"); 复杂度为O(n) ## 按照因子计算 我们思考一个数的因子，假如一个数n的一个因子a,那么我们可得n/a=b,b为整数。 所以a\*b=n. 假设a<=b,那么a<=√n，因此，如果a不存在，那么b也不存在，即因子存在一一对应关系，所以我们只要判断<=√n的数即可。 int n,i; for(i=2;i*i<=n;i++){ if(n%i==0){ break; } } if(i*i>n) printf("%d is a prime\n"); else printf("%d isn't a prime\n"); 复杂度为O( sqrt(n) ) ,满足一般运算的要求了。 ## 费马小定理 参见词条**费马小定理**