首页
社区
课程
招聘
问答 CTF 排行榜 知识库 工具下载 看雪峰会 看雪商城 证书查询
  1. 社区
  2. 付费问答
    3. 发新帖
[旧帖] [求助]素数的疑问的验证问题 0.00雪花
发表于: 2009-5-4 22:03 3654

[旧帖] [求助]素数的疑问的验证问题 0.00雪花

因帅被砍 活跃值
2009-5-4 22:03
3654
在以往判断一个数n是不是素数时,我们都是采用i从2到sqrt(n)能否整除n，
为何sqrt(n)以后的数字不用验证呢，为什么不一直验证到n呢？
能用数学方法表示 一下么？

[培训]《安卓高级研修班(网课)》月薪三万计划，掌握调试、分析还原ollvm、vmp的方法，定制art虚拟机自动化脱壳的方法

收藏
免费 ・0
支持
分享
最新回复 (8)
gaouestc
雪    币： 285
活跃值： (10)
能力值： ( LV2，RANK：10 )
在线值：
发帖
回帖
粉丝
私信
2 楼
不一直验证到n是为了提高下效率
若一个数不是素数则可分解为一个<=sqrt(n)的数乘以一个>=sqrt(n)的数
2009-5-4 22:11
0
rockinuk
雪    币： 2096
活跃值： (100)
能力值： (RANK：420 )
在线值：
发帖
回帖
粉丝
私信
3 楼
是的。同意 gaouestc 所說，只要驗證到 sqrt(n) 即可。
2009-5-4 22:23
0
曾定国
雪    币： 198
活跃值： (13)
能力值： ( LV4，RANK：50 )
在线值：
发帖
回帖
粉丝
私信
4 楼
有时候如果有一部分素数表，则只要 将 2 到 sqrt(n) 之间的素数除一遍
2009-5-4 22:53
0
tianci
雪    币： 247
活跃值： (131)
能力值： ( LV2，RANK：10 )
在线值：
发帖
回帖
粉丝
私信
5 楼
学习了！谢谢大家…
2009-5-4 23:27
0
圣新冰心
雪    币： 59
活跃值： (10)
能力值： ( LV2，RANK：10 )
在线值：
发帖
回帖
粉丝
私信
6 楼
学习了，不错的解释
2009-5-5 09:23
0
圣新冰心
雪    币： 59
活跃值： (10)
能力值： ( LV2，RANK：10 )
在线值：
发帖
回帖
粉丝
私信
7 楼
同时>=sqrt(n)的数不会超过n/2
2009-5-5 09:25
0
xtjjcel
雪    币： 200
活跃值： (10)
能力值： ( LV2，RANK：10 )
在线值：
发帖
回帖
粉丝
私信
8 楼
其实 数学可以证明只需筛到sqrt(n).
既成的定理 拿来用就是了 如果想要知道原理 查看相关资料
2009-5-5 23:00
0
cxyOOOO
雪    币： 228
活跃值： (10)
能力值： ( LV2，RANK：10 )
在线值：
发帖
回帖
粉丝
私信
9 楼
条件，n 在<sqrt(n)的自然数中没有质因数，M > sqrt(n),
设M 是 n的质因数，则L = n / M < n / sqrt(n) = sqrt(n)，与条件矛盾
2009-5-6 15:27
0
游客
登录 | 注册 方可回帖
回帖 表情 雪币赚取及消费
高级回复
返回
//