绝响
绝响
题解
题解 | #完全数计算#
全部文章
题解
归档
标签
去牛客网
登录
/
注册
题解 | #完全数计算#
134 浏览
0 回复
2022-04-02
绝响
+关注
完全数计算
http://www.nowcoder.com/practice/7299c12e6abb437c87ad3e712383ff84
百度完全数得到了一个推导公式,能有效的降低运算花费的时间。
“大数学家
欧拉
曾推算出完全数的获得公式:如果p是
质数
,且2^p-1也是质数,那么(2^p-1)X2^(p-1)便是一个完全数。”
https://baike.baidu.com/item/%E5%AE%8C%E5%85%A8%E6%95%B0/370913?fromtitle=%E5%AE%8C%E5%A4%87%E6%95%B0&fromid=9450205#5_1
那么整体分成3步来做
Step1 找到1-5*10^5之间,满足
(2^p-1)X2^(p-1)<=
5*10^5的数
Step2 剔除掉
Step1结果中非质数的数
Step3 从
Step2的结果集中剔除掉
2^p-1非质数的数
剩下的样本即
1-5*10^5之间,满足公式的p值;其个数也等同于
1-5*10^5之间完全数的个数。
Python3
举报
收藏
赞
评论加载中...