Shulou(Shulou.com)06/01 Report--

Editor to share with you how to solve the problem of perfect numbers in leetcode, I believe that most people do not know much about it, so share this article for your reference, I hope you can learn a lot after reading this article, let's go to know it!

Topic link

Https://leetcode-cn.com/problems/perfect-number/

Topic description

For a positive integer, we call it a "perfect number" if it is equal to the sum of all positive factors except itself.

Given a positive integer n, if it is a perfect number, return True, otherwise return False

Example:

Enter: 28

Output: True

Explanation: 28 = 1 + 2 + 4 + 7 + 14

Note:

The number n entered will not exceed 100000000. (1e8)

The idea of solving the problem

Tags: math

First of all, because of the definition of the perfect number, we need to exclude itself, so the number 1 must not be a perfect number.

Secondly, we need to calculate the sum sum of all positive factors of num except itself. Positive factors must appear in pairs, so we only need to traverse to the square root sqrt of num.

Take 36 as an example, its non-self positive factors are 1, 2, 3, 4, 6, 9, 12, 18, in which 1 and 6 are calculated separately, and [2, 18], [3, 12], [4, 9] are all corresponding.

So you only need to traverse to the square root 6 of 36 to get all the positive factors.

1 the reason for separate calculation is to exclude itself, and the reason for separate calculation for 6 is 6 * 6 = 36, the two values are the same, so it can only be calculated once.

Time complexity: O (logn), n is the size of num

Tips: the perfect number is only 6,28,496,8128 and 33550336, which can be solved by judging whether the number is the following.

Code

Java version

Class Solution {

Public boolean checkPerfectNumber (int num) {

If (num = = 1) {

Return false

}

Int sum = 1; / / A positive integer must have a 1, without thinking about itself, so handle it separately.

Int I = 2

Double sqrt = Math.sqrt (num)

For (; I)

< sqrt;i++) { if(num % i == 0) { sum += i; sum += num / i; } } // 此处单独处理的原因在于只需要加1次i值，如果在循环中会加2次 if(i * i == num) { sum += i; } return sum == num; } } JavaScript版本 /** * @param {number} num * @return {boolean} */ var checkPerfectNumber = function(num) { if(num == 1) { return false; } let sum = 1; // 正整数一定会有一个1，同时不用考虑自身，所以单独处理 let i = 2; const sqrt = Math.sqrt(num); for(;i < sqrt;i++) { if(num % i == 0) { sum += i; sum += num / i; } } // 此处单独处理的原因在于只需要加1次i值，如果在循环中会加2次 if(i * i == num) { sum += i; } return sum == num; }; 画解

The above is all the contents of the article "how to solve the problem of perfect numbers in leetcode". Thank you for reading! I believe we all have a certain understanding, hope to share the content to help you, if you want to learn more knowledge, welcome to follow the industry information channel!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.