【数学】C038_完美数（暴力枚举 | 开平方优化 | 欧几里得定理）

Natalie ·

更新时间:2024-11-15

· 637 次阅读

一、题目描述

We define the Perfect Number is a positive integer that
is equal to the sum of all its positive divisors except itself.
Now, given an integer n,
write a function that returns true when it is a perfect number and false when it is not.
Example:
Input: 28
Output: True
Explanation: 28 = 1 + 2 + 4 + 7 + 14
Note: The input number n will not exceed 100,000,000. (1e8)

二、题解 (1) 暴力枚举（超时）

/**
 * @thought：暴力枚举（99999997）
 * @date: 1/18/2020 10:56 AM
 * @Execution info：
 *  ·执行用时  ms 击败了 % 的java用户
 *  ·内存消耗 MB 击败了 % 的java用户
 * @Asymptotic Time Complexity：O(根号num)
 */
public boolean checkPerfectNumber(int num) {
  int sum=0;
  for (int i = 1; i < num; i++) {
    if(num%i==0)
      sum+=i;
  }
  return sum==num;
}

复杂度分析 时间复杂度： O(num)O(num)O(num)，空间复杂度：O(1)O(1)O(1)， (2) 优化暴力

在枚举时，我们只需要从 111 到 sqrt(n)sqrt(n)sqrt(n) 进行枚举即可。因如果 n 有一个小于 N (sqrt(n))N\ (sqrt(n))N (sqrt(n)) 的因数 x1x1x1，那么它一定有一个大于 N (sqrt(n))N\ (sqrt(n))N (sqrt(n)) 的因数 x2 (n/x1)x2\ (n/x1)x2 (n/x1)。

此外还需要考虑特殊情况，即 x=n/xx = n/xx=n/x，这时我们不能重复计算。因为 N∗N==nN*N==nN∗N==n，如果 x1<N，那么x2>Nx1Nx1N

/**
 * @date: 1/18/2020 11:01 AM
 * @Execution info：
 *  ·执行用时 6ms -> 2ms 击败了 32.44% -> 87.68% 的java用户
 *  ·内存消耗 MB 击败了 46.42% 的java用户
 * @Asymptotic Time Complexity：O()
 */
public boolean checkPerfectNumber2(int num) {
  if(num==1)  return false;
  int sum=1;
  double sqltNum = Math.sqrt(num);
//    for (int x = 2; x <= sqltNum; x++) {
//      if(num%x==0)
//        sum+=x + num/x;
//    }
  for (int x = 2; x *x <= num; x++) {
    if(num%x==0)
      sum += x + num/x;
  }
  return sum==num;
}

复杂度分析 时间复杂度： O(sqrt(num))O(sqrt(num))O(sqrt(num)) 空间复杂度： O(1)O(1)O(1)
作者：PANjj99

开平方欧几里得枚举数学优化

1024 个赞