关于判断质数只需要到n/2或到根号n的原理 |
您所在的位置:网站首页 › 判定一个数是否为素数的方法有哪些 › 关于判断质数只需要到n/2或到根号n的原理 |
这个问题从我接触为止就成了我的心头结,现将其证明整理,感谢那些我为提供思路的同学,比如煌星。 首先1不是质数,1原本被数学家作为质数,但是有些特殊的数可以被几个质数相乘得到的结果相同,如果1是则有多解,任何答案它都可以插一脚,所以被数学家忍痛剔除。 质数的定义即为除1和本身外不能被其他数整除的数,带有特殊性质(质数)。 那么判断质数只要从2到本身前进行试除,能整除即不是。这是最基本的判断。 那么为什么只要判断到n/2呢? 假设数为N,则N = 1*N(N是其最大因数)= 2 * (n/2)(n/2是其第二大因数) = 3 * (n/3) = 4 * (n/4)...... 且因数为正整数。 #define _CRT_SECURE_NO_WARNINGS 1 #include int main() { int i = 0; int j = 0; for (i = 2; i |
今日新闻 |
点击排行 |
|
推荐新闻 |
图片新闻 |
|
专题文章 |
CopyRight 2018-2019 实验室设备网 版权所有 win10的实时保护怎么永久关闭 |