首页 > 试题广场 >

完全数计算

[编程题]完全数计算
  • 热度指数：145363 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解

完全数（Perfect number），又称完美数或完备数，是一些特殊的自然数。

它所有的真因子（即除了自身以外的约数）的和（即因子函数），恰好等于它本身。

例如：28，它有约数1、2、4、7、14、28，除去它本身28外，其余5个数相加，1+2+4+7+14=28。

输入n，请输出n以内(含n)完全数的个数。

数据范围：

输入描述:
输入一个数字n


输出描述:
输出不超过n的完全数的个数
示例1

输入

1000

输出

3
算法知识视频讲解
添加回答
Python
牛客335611430号头像 牛客335611430号
while 1:
    try:
        n=int(input())
        pnn=0
        for mm in range(1,n+1): #calculate perfact number
            sum = 0
            for s in range(1,mm):
                if mm%s==0:sum+=s
            if sum==mm:pnn+=1
        print( pnn)
    except:break
发表于 2021-04-04 21:51:32 回复(1)
Python
LyiHaoTX头像 LyiHaoTX 
while True:
    try:
        n = int(input())
        num = 0
        for i in range(1, n):
            s = []
            for j in range(1, i):
                if i % j == 0:
                    s.append(j)
            if sum(s) == i:
                num += 1
        print(num)
    except:
        break
朴实无华
发表于 2021-03-23 23:51:14 回复(2)
Python
爱吃饭团.Deus头像 爱吃饭团.Deus
#除了33550336时间太长，其他都能过
Perfect_number=list()
while True:
    try:
        Perfect_number.append(int(input()))
    except:
        break
for i in range(0,len(Perfect_number)):
    if Perfect_number[i]<6:
        print(0,end='\n')
        break
    count=0
    for k in range(Perfect_number[i],5,-1):
        cal=list()
        cal.append(1)
        for j in range(int(k**1/2),1,-1):
            if k%j==0:
                cal.append(j)
                cal.append(k/j)
        cal=list(set(cal))
        if sum(cal)==k:
            count+=1
    print(count,end='\n')
发表于 2021-03-15 21:41:07 回复(0)
Python
星凌九天头像 星凌九天
while True:
    try:
        num=int(input())
        n=0
        for i in range(2,num+1):
            k=0
            for j in range(1,i//2+1):
                if i%j==0:
                    k+=j
            if k==i:
                n+=1
        print(n)
    except:
        break
发表于 2021-03-14 21:04:50 回复(1)
Python
肖大神头像 肖大神 
import sys
for n in sys.stdin:
    n=int(n)
    total=0
    for num in range(1,n+1):
        yinzi=[]#因子列表
        for i in range(1,num+1):#i是分母不可为零，但i可为它本身
            if num%i==0:
                yinzi.append(i)
        if yinzi and sum(yinzi[0:-1])==yinzi[-1]:#若因子不为空且前几个因子相加等于最后一个数
            total+=1
    print(total)

发表于 2021-02-21 21:40:31 回复(0)
Python
牛客705933698号头像 牛客705933698号
def num(n):
    list1 = []
    for i in range(1,n+1):
        if n % i == 0:
            list1.append(i)
    if sum(list1) - n == n:
        return True
    else:
        return False 
    
while True:
    try:
        a = int(input())
        res = 0
        for j in range (1,a+1):
            if num(j):
                res+=1
            else:
                continue
        print(res)
    except:
        break

发表于 2021-01-27 16:55:51 回复(0)
Python
JeremyStar头像 JeremyStar 
def is_perfectNum(num):
    L = []
    for i in range(1,num):
        if num % i == 0:
            L.append(i)
    if sum(L) == num:
        return True
    return False

while True:
    try:
        n = int(input().strip())
        if 0 < n <= 500000:
            count_perfectNum = 0
            for i in range(1, n+1):
                if is_perfectNum(i):
                    count_perfectNum += 1
            print(count_perfectNum)
    except:
        break

方法一（上述方法）：直接给出判断完全数的方法，然后以遍历的方式，一个一个地找完全数
方法二：利用欧拉公式——如果i是质数，2^i-1也是质数，那么(2^i-1)*2^(i-1)就是完全数 
def checkprime(num):
    if num == 1:
        return False
    list1 = []
    for i in range(2, num):
        if num % i == 0:
            list1.append(i)
    if not list1:
        return True
    else:
        return False

while True:
    try:
        n = int(input())
        res = []
        for i in range(1, n+1):
            if (2**i-1)*2**(i-1) > n:
                break
            elif checkprime(i) and checkprime(2**i-1):
                res.append((2**i-1)*2**(i-1))
        print(len(res))
    except:
        break
编辑于 2020-12-06 17:46:11 回复(0)
Python
乐观的lishan头像 乐观的lishan 
# Python3单纯的遍历解法，算法过程清晰明了，运行时间850ms~900ms
# 判断一个数是否为完全数
def perfect_number(num):
    add = 0
#   遍历寻找真因子约数
    for i in range(1, num):
        if num % i == 0:
            add += i 
#           所有真因子约数之和已经大于这个数本身
            if add > num:
                break
    if add == num:
        return True
    else:
        return False

while True:
    try:
        n = int(input())
        cnt = 0
#       遍历寻找完全数
        for i in range(1,n+1):
            if perfect_number(i):
                cnt += 1
        print(cnt)
    except:
        break
       

编辑于 2020-11-13 23:35:33 回复(0)
Python
公子i吃鱼头像 公子i吃鱼
欧拉筛素数 结合 欧拉公式，python 用时24ms 
def primeList(n:int):
    # 欧拉筛素数 时间复杂度 o(n)
    num = [True for i in range(n + 1)]
    prime = []
    for i in range(2, n + 1):
        if num[i]:
            prime.append(i)
        for j in prime:
            if i * j > n:
                break
            num[i * j] = False
            if i % j == 0:
                break
    return prime, num

while True:
    try:
        n = int(input().strip())
        res = 0
        prime, num = primeList(n)
        for i in prime:
            tmp = 2 ** i - 1
            if tmp > n:
                break
            if num[tmp]:
                # 欧拉公式 判断完全数
                perfect_num = tmp * (2 ** (i - 1))
                if perfect_num > n:
                    break
                res += 1
        print(res)
    except:
        break


编辑于 2020-10-21 11:39:10 回复(0)
Python
牛客490386548号头像 牛客490386548号 
#用例用了1.3s，3M内存。勉强通过，但是底下试试50000，几十秒了，4各完美数
#50000
#[6, 28, 496, 8128]

while True:
    try:
        number = int(input())
        perfectNum = []
        for num in range(6, number + 1):
            factor = []
            sumCount = 0
            # print(num)
            for i in range((num+1)//2):
                if num % (i+1) == 0:
                    factor.append(i + 1)
            # print('factor: ', factor)
            for i in factor:
                sumCount += i
            # print('sumCount: ', sumCount)
            if sumCount == num:
                perfectNum.append(num)
        print(perfectNum)
        print(len(perfectNum))

    except EOFError:
        break

发表于 2020-09-30 23:35:24 回复(0)
Python
牛客902100313号头像 牛客902100313号
def inshu(n):
    list1 = []
    for i in range(1,n):
        if n % i == 0:
            list1.append(int(i))
    return list1

def wanquan(n):
    t = 0
    for i in range(2,n+1):
        if sum(inshu(i)) == i:
            t += 1
    return t


while True:
    try:
        n = int(input())
        if n == 1:
            print('0')
        elif n <= 0:
            print('-1')
        else:
            print(wanquan(n))
    except:
        break
发表于 2020-09-14 17:42:02 回复(0)
Python
牛客luckylulu头像 牛客luckylulu
 解法一： 循环遍历：每个数从1到它本身整除，整除的数放进set()集合，去除重复元素 ，并求除它自身以外的和  。 结果： 单纯遍历在当N大于5000时会引起超时。寻找其他解法。
解法二：采用讨论版块里欧拉公式求解，如果i是质数，2^i-1也是质数，那么(2^i-1)*2^(i-1)就是完全数。
# 6=2×3=2×(2^2-1)
# 28=4×7=2^2×(2^3-1)
# 496=16×31=2^4×(2^5-1)
# 8128=64×127=2^6×(2^7-1)
# 人们知道完全数有什么用呢？

# 6=2×3=2×(2^2-1)

# 28=4×7=2^2×(2^3-1)

# 496=16×31=2^4×(2^5-1)

# 8128=64×127=2^6×(2^7-1)

# 寻找其他解法
# 利用欧拉的公式：如果i是质数，2^i-1也是质数，那么(2^i-1)*2^(i-1)就是完全数
import sys

def checkprime(num):
    if num ==1 :
        return False
    lis1 = []
    for i in range(2, num):
        if num%2 == 0:
            lis1.append(i)
    if not lis1:
        return True
    else:
        return False

if __name__ == '__main__':
    for line in sys.stdin:
        n = int(line)
        res = []
        for i in range(1,n+1):
            if (2**i-1)*2**(i-1)>n:
                break
            elif checkprime(i) and checkprime(2**i-1):
                res.append((2**i-1)*2**(i-1))

        print(len(res))
    
    
# 完全数
# 循环遍历  每个数从1到它本身整除，整除的数放进set()集合，去除重复元素   并求除它自身以外的和
# 单纯遍历会引起超时

'''
    yueshu = []
    yueshu.append(1)  # 任何自然数都能被1整除
    k = 0 # 完全数结果

    for i in range(3, n):
        yueshu = [1]
        for j in range(2, i):
            if i % j == 0:
                yueshu.append(j)
                yueshu.append(i/j)
            else:
                continue

        if sum(set(yueshu)) == i:
            k = k + 1
            print(i)
    print(k)
'''



发表于 2020-09-10 21:05:00 回复(0)
Python
kite97头像 kite97 
while True:
    try:
        n ,res,sum = int(input()),0,0
        for i in range(1,n + 1):
            for j in range(1, int(i / 2) + 1):
                if(i % j == 0):
                    sum +=j
            if sum == i:
                res += 1
            sum = 0
        print(res)
    except:
        break
优化有点麻烦，时间有点长，好像到平方根就好了
发表于 2020-09-02 17:06:42 回复(0)
Python
DD.KE369头像 DD.KE369
def func(b):
    ls = []
    for i in range(1, b//2+1):
        if b%i==0:
            ls.append(i)
    if sum(ls)==b:
        return 1
    else:
        return 0
while True:
    try:
        a = int(input())
        res=0
        for i in range(1, a+1):
            res+=func(i)
        print(res)
    except:
        break
发表于 2020-09-02 16:15:43 回复(0)
Python
AIHuiliu头像 AIHuiliu 
while True:
    try:
        n = int(input())
        if n <= 0:
            break
        globnum = 0
        for i in range(1,n+1):
            if i % 2 != 0:
                continue
            sumnum = 0
            for j in range(1,i):
                if i % j == 0:
                    sumnum += j
            if sumnum == i:
                globnum += 1
        print(globnum)
    except:
        break
编辑于 2020-08-30 17:57:34 回复(0)
Python
JaquesJames头像 JaquesJames
写双重for循环，时间略长 
while True:
    try:
        n = int(input())
        res = 0
        for i in range(1, n):
            sum_num = 0
            for j in range(1, i//2 + 1):
                if i%j == 0:
                    sum_num += j
            if sum_num == i:
                res += 1
        print(res)
    except:
        break


发表于 2020-08-22 20:20:46 回复(0)
提交观点

问题信息

基础数学
难度：
56条回答 30243浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号