前言

今天一个当老师的同学问我判断一个数是不是素数？用代码怎么实现？突然懵了，素数是什么？

质数

质数（prime number）又称素数，有无限个。质数定义为在大于1的自然数中，除了1和它本身以外不再有其他因数。那要怎么判断呢？是不是一个个除判断是否有余数？是不是还有更简单的方法？

假设n不是素数，那应该有n=a*b（a、b、n都是正整数，且n>a>1和n>b>1），那么根号n和a、b有什么关系呢？

由不是素数的等式n=a*b，可以出现两种情况：

1、如果a=b=根号n，那么我只要判断n除以根号n，余数为0,就可以认为它不是素数。

2、如果a>根号n且b>根号n，那么a*b > 根号n × 根号n =n，这种情况是一定不存在的，因为我们的前提是n不是素数n=a*b。

因此可以判断a和b中，至少要有一个小于根号n。

总结

因此判断一个正整数n是不是素数，只要n跟2到根号n取余，如果出现0，说明可以除尽，存在因数，就可以证明它不是素数。

代码实现