动脑时间-一个数学问题,用python代码实现-判断素数

前言

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

动脑时间-一个数学问题,用python代码实现-判断素数


质数

质数(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是不是素数,只要n2到根号n取余,如果出现0,说明可以除尽,存在因数,就可以证明它不是素数。

动脑时间-一个数学问题,用python代码实现-判断素数


代码实现

动脑时间-一个数学问题,用python代码实现-判断素数

相关推荐