水木社区手机版
- 主题:Re: 怎么证明?不准用计算机程序蛮力干。
- 查质数表可知。
如果一个数是不是质数有方法可以证明，那么寻找大质数也没那么难了
【 在 king73 的大作中提到: 】
: [upload=1][/upload]
--
FROM 39.149.15.* - 没有那么大的质数表吧？我搞到的质数表，只有1 到999亿之间的质数表。
【 在 upndown 的大作中提到: 】
: 查质数表可知。
: 如果一个数是不是质数有方法可以证明，那么寻找大质数也没那么难了
:
: ...................
--
FROM 120.242.238.* - 能用计算机在短时间证明出来，就不错了。。。
【 在 king73 的大作中提到: 】
: [upload=1][/upload]
--
FROM 120.242.238.* - 这个概率算法，有可能出错。。。。
【 在 king73 的大作中提到: 】
:
[upload=1][/upload]
--
FROM 120.242.238.* - 你说的是一般情况。对某个特定的数，这个逻辑没有意义
【 在 upndown 的大作中提到: 】
: 查质数表可知。
: 如果一个数是不是质数有方法可以证明，那么寻找大质数也没那么难了
:
: ...................
--
FROM 211.161.245.* - 这个数有个特点，可以表示成a*b*10+1的形式。
【 在 king73 的大作中提到: 】
: [upload=1][/upload]
--
FROM 49.5.217.* - 一般的题目都是要求你证明某个数不是素数的，因为你找到一个因数就够了
要证明某个数是素数没啥好办法，就拿这题来说，真的要尝试所有小于sqrt（1111111111111111111）的素数都不能整除1111111111111111111。而小于sqrt（1111111111111111111）的素数大约有sqrt（1111111111111111111）/ln（sqrt（1111111111111111111））,大约是50736200个素数。
另外的算法是miller-rabin素性检验，但是这个检验算法只能保证某个数有很大的概率是素数，可能会出现误判。
【 在 king73 的大作中提到: 】
: [upload=1][/upload]
--
FROM 58.135.80.* - 预先算好质数表，存在数据文件里；运行程序时，“查表可知”。。。
--
FROM 120.244.234.*