作业帮历史上有没有人解决过素数函数?有什么经验教训?知道多少 说多少 如果没有人知道 那么 只好把积分送给自己了
来源：学生作业帮助网 编辑：作业帮 时间：2024/11/20 18:45:38
历史上有没有人解决过素数函数?有什么经验教训?知道多少 说多少 如果没有人知道 那么 只好把积分送给自己了
历史上有没有人解决过素数函数?
有什么经验教训?
知道多少 说多少 如果没有人知道 那么 只好把积分送给自己了
历史上有没有人解决过素数函数?有什么经验教训?知道多少 说多少 如果没有人知道 那么 只好把积分送给自己了
你的问题本身就是有问题的.
因为测试一个数字是否是素数,本身就是一个很简单但也很费时的事情.
最简单的正确函数就是：
bool test( 数字 n ){
从2开始到n-1, 对n进行试除；
若某个数字能除净,return false ;
else return true ;
}
这个算法虽然简单,但是有一个致命的弱点.
A：效率低,如果给一个大数字,你自己去算算吧,看你算到猴年马月……
B：计算机上可能无法实现——如果遇到这种情况：数字长度大于了计算机能存储的最大数字.
不过,这个素数算法绝对正确!
然后跟你说些实际的：
1：如果单单考虑不是很变态的素数本身的话,那么早就解决了,而且是目前的一个很好的素数筛选法——厄拉多塞定理就可以.
简而言之,就是从2开始,排除所有2的倍数；然后排除3的倍数；……；以此类推；就这样,当你进行到排除X的倍数的时候,X之前的所有素数你都知道了.
相关的厄拉多塞定理,楼主可以上网去搜,或者《数论》书里有.
2：实际上,计算素数,不可能考虑素数无限大,至少你作为一个个人,即使使用着性能超好的微机,也最多只能考虑有限长度的素数.
现在的计算机是32位,可以计算2^32以内的素数,也就是42亿以内的素数.然后如果拓展了,就可以使用64位,可以计算2^64以内的素数（42亿乘以42亿~自己算范围是多大吧）.由于现在操作系统位数的限制,目前的水准也就是这么多的了.当然啦,如果要确定2^64以内的任意一个数字是不是素数,可就不是这么的用厄拉多塞了,而是用到拉宾-米勒算法和Pollard启发式算法了.具体的参见算法书和某些数论书.
3：大于2^64位的素数,计算机不是不能算.但是时间复杂度要比64位以内的数字要高不是一丁点.这个如果你学了编程就知道了——64位以上的需要数组,而不是单单一个什么整型就能搞定了.
要更长度的,得需要专业领域的人们来解答.
所以,综合而言,
1：类似于你这样很笼统的问素数函数,那么古人就已经很笼统的正确回答了.参考我上面的test()函数以及厄拉多塞定理.
2：真正需要解决的是如何高效地测试某个数字是否是素数,特别是很长的数字.
3：经验教训,就是,数学方面的每个问题都是一个既简单又复杂的问题.门外汉,包括你我,最多也只能研究到和我差不多的这个程度了,很简单吧~但是,那还是一个数学顶尖领域,不过就不是我们普通人能研究能想象的……我现在和你讨论的最长长度是64位二进制,专家们研究的是几千几万长度的二进制和其他优化算法,诸如AKS素数测定算法等……那个算法我是看不懂,很科幻级别.而且,你稍微有一丁点小突破,就可以发包论文并且在这方面树立权威了,就这种程度.
4: 不存在你所谓的“如果没有人知道”,只是有些人不想回答；有些人,像我这样的菜鸟,看着这样的话不大舒服,就来献丑丢脸面.其实,网络虽然是一个虚拟大平台,但也需要大家用心维护,体现出自己的真性情.这么个说法没必要（虽然感觉也蛮正常的）~