【科普】-求素数为什么只需要求到平方根就行？_数论求素数平方根

作者：我家自动化 | 2024-03-27 18:56:25

踩

数论求素数平方根

素数是什么

一个大于1的正整数，如果除了1和它本身以外，不能被其他正整数整除，就叫做素数。

感性认识

基于素数的定义，此文的所有数都是大于1的数
首先来回忆一个恒等式（x>1）：(根号x)*(根号x)=x
（根号x）一定大于1，因为x>1。
假设a*b=x
如果a<（根号x）而且b<（根号x）那么一定有a*b<(根号x)*(根号x)
如果a>（根号x）而且b>（根号x）那么一定有a*b>(根号x)*(根号x)
所以如果两个因数不相等的话，那么两个因数一定是一个比（根号x）大，一个比（根号x）小。

理性逻辑

此时有两个数a,b满足a*b=x
假设a<=(根号x)，即（a/根号x）<=1
则a*b=x两边同时除以（根号x）得到（a/根号x）*b=(根号x)，
两边同时除以b得到 1=>（a/根号x）=(根号x/b)。
得到(根号x)/b<=1也就是（根号x）<=b
由a<=(根号x)得到（根号x）<=b说明（根号x）必定在两个因数中间。

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/我家自动化/article/detail/326335

【科普】-求素数为什么只需要求到平方根就行？_数论求素数 平方根

素数是什么

感性认识

理性逻辑

【科普】-求素数为什么只需要求到平方根就行？_数论求素数平方根