利用欧几里得-欧拉定理解决完美数 问题
1.什么叫完美数:对于一个 正整数,如果它和除了它自身以外的所有 正因子 之和相等,我们称它为 「完美数」
2.解题思路:我们最先考虑的一定是利用枚举算法求出质数并求和进行判断
python
if num == 1:
return False
total = 1
for i in range(2, int(math.sqrt(num)) + 1):
if num % i == 0:
total += (i + num // i)
return total == num
欧几里得-欧拉定理:目前未发现奇完美数,所以偶完美数一定存在以下关系
梅森素数
当N<
只需要带入2, 3, 5, 7, 13, 17, 19, 31计算便可得出,时间复杂度和空间复杂度均为O(1)
int[ ] primes = new int[]{2, 3, 5, 7, 13, 17, 19, 31};
for (int prime : primes) {
if (pn(prime) == num) {