C#版 - Leetcode 507. 完美数 - 题解

Enjoy233

发布于 2019-03-05 15:42:38

7730

发布于 2019-03-05 15:42:38

文章被收录于专栏：大白技术控的技术自留地

C#版 - Leetcode 507. 完美数 - 题解

507.Perfect Number

在线提交: https://leetcode-cn.com/problems/perfect-number/

题目描述

对于一个 正整数，如果它和除了它自身以外的所有正因子之和相等，我们称它为“完美数”。

给定一个 正整数 n，如果他是完美数，返回 True，否则返回 False

示例：

输入: 28
输出: True
解释: 28 = 1 + 2 + 4 + 7 + 14

注意:

输入的数字 n 不会超过 100,000,000. (1e8)

题目难度：Easy
通过次数：492
提交次数：1.9K
相关话题数学相似题目自除数

思路: 方法1: 如果num有约数d，则它必有约数num/d，与判断素数时的sqrt的功能类似。因而只需存一半的值即可~

方法2: 完美数有数学公式，第n个完美数为Pn=(2p−1)⋅2p−1Pn=(2p−1)⋅2p−1P_n = (2^p - 1)\cdot 2^{p-1} .

6, 28, 496, 8128 - OEIS(用于收录整数数列规律的在线百科) https://oeis.org/search?q=6%2C+28%2C+496%2C+8128&sort=&language=&go=Search

Tips: 遇到整数相关的问题，考虑到OEIS网站的站内搜索功能太弱，可以使用Google site命令搜索该英文名，比如: Perfect numer site:oeis.org

已AC代码:

public class Solution
{
    public bool CheckPerfectNumber(int num)
    {
        if (num == 1)
            return false;

        List<int> divisors = new List<int>();
        for (int i = 2; i*i <= num; i++)        // store the smaller one in divisor pair, then another is num/smaller
        {
            if (num % i == 0)
                divisors.Add(i);
        }

        int sum = 1;    // 1 is divisor of any integer
        foreach (var divisor in divisors)
            sum += divisor + num/divisor;
        return num == sum;
    }
}

Rank:

You are here! Your runtime beats 92.45 % of csharp submissions.

将List换为Array，或将num%i换为num - (num/i) * i，运行速度并没提升~

public class Solution
{
    public bool CheckPerfectNumber(int num)
    {
        if (num == 1)
            return false;

        int[] divisors = {};
        for (int i = 2; i*i<=num; i++)  // Store the smaller one in divisor pair, then another is num/smaller
        {
            if (num - (num/i) * i == 0)
                divisors = divisors.Concat(new int[]
                {
                   i
                }).ToArray();
        }

        int sum = 1;   // 1 is divisor of any integer
        foreach (var divisor in divisors)
            sum += divisor + num/divisor;
        return num == sum;
    }
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2018年06月22日，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

编程算法

登录后参与评论

0 条评论

热度