首页 > 试题广场 >

完全数计算

[编程题]完全数计算

热度指数：144022 时间限制：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)完全数的个数。

数据范围： $1 \le n \le 5 \times 10^{5} \$

输入描述:

输入一个数字n

输出描述:

输出不超过n的完全数的个数

示例1

输入

输出

算法知识视频讲解

Python

朝夕_

while True:
  try:
    a,b,c = int(input()),0,[]
    for i in range(4,a+1):
      for j in range(1,int(i**0.5)+1):
        if i%j == 0:
          b += j + int(i//j)
      if b == 2*i:
        c.append(i)
        b = 0
      else:
        b = 0
    print(len(c))
  except:
    break

发表于 2020-02-20 21:34:51 回复(4)

牛客-120抢救中心

import java.util.Scanner;
public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()) {
            int n = sc.nextInt();
            int cnt = 0;
            while((n--)>1) {
                int number = 0;
                for(int i=1; i<n; i++) {
                    if(n%i==0) {
                        number += i;
                    }
                }
                if(n == number) {
                    cnt++;
                }
            }
            if(cnt != 0)
                System.out.println(cnt);
            else
                System.out.println(-1);
        }
    }
}

发表于 2018-10-06 19:01:15 回复(0)

Hmmmmmmm_y

#include <bits/stdc++.h>
 using   namespace std;
int fun(int n)
{
    int cnt=0;
    if(n>500000 || n<=0) return -1;
    else
    {
        
        for(int i=2;i<=n;i++)
        {
            int sum=0;
            for(int j=2;j<sqrt(i);j++)
            {
                if(i%j==0)
                {
                    if(i/j==j) sum+=j;
                    else
                    {
                        sum+=j;
                        sum+=(i/j);
                    }
                }
            }
            if(sum+1==i) cnt++;
        }
    }
    return cnt;
}
int main()
{
    int n;
    while (cin >>n)
    {
        cout<<fun(n)<<endl;
    }
    system("pause");
    return 0;
}

发表于 2018-08-20 14:13:46 回复(0)

风逝cherish

#include <iostream>
#include <math.h>
#include <string.h>
using namespace std;

int main(){

   int n;
   int count = 0;

   int tmp[100];
   while (cin >> n){

       if (n > 0 && n <= 50000){
            int a = 0;
           while (n > 1){
               memset(tmp, 0, sizeof(tmp));
               for (int i = 2; i <= sqrt(n); i++) //降低复杂度
               {
                   if (n % i == 0)
                   {
                       if (n % i == i)
                       {
                           tmp[count++] = i;
                       }
                       else
                       {
                           tmp[count++] = i;
                           tmp[count++] = n / i;
                       }
                   }
               }

               int sum = 1;
               for (int i = 0; tmp[i]; i++)
               {
                   sum += tmp[i];
               }
               if (sum == n)
               {
                   a++;
               }
               n--;
               count = 0;
           }
           cout << a << endl;
       }
       else
       {
           return -1;
       }
   }

   return 0;
}

发表于 2017-08-18 23:26:02 回复(0)

viod

#include<stdio.h>
#include<math.h>
int main() {
int num;
while(~scanf("%d", &num)){
    if(num==1){printf("0\n");break;}
    int count = 0;
    for(int i=2; i<=num; i++){
        int sum = 1,root = sqrt(i); // 求约数遍历到根值即可
        for(int j=2; j<=root; j++){
            if(i%j==0){
                sum +=j; //与约数j相加
                if(i!=root) //防止两个相同的约数重复计算
                    sum +=(i/j); //与约数j对应点另一个约数相加
            }
        }
        if(sum == i)count++;
    }
    printf("%d\n", count);
}
}

发表于 2022-03-29 20:32:28 回复(0)

Python 3

雷姆的心动男孩

一遍过的，可能有点麻烦，之前遇到过类似的，直接分享了思路：

while True:
    try:
        n = int(input())
        l_n = []  # 用于储存不大于n的完全数
        for i in range(5, n+1):     #最小的完全数是6 = 1+2+3，所以从5开始，循环是为了判断每个不大于n的数是不是完全数
            l_f = []              # 用于储存每次循环的 i 的因子
            for j in range(2, int(i**0.5)+1):     # 找i不含自身的因子，i**0.5 相当于 i开方
                if i % j == 0:               # 如果j 是 i 的因子 ，就把j 和 i//j储存起来
                    l_f.append(j)
                    l_f.append(i // j)
            if i == 1 + sum(l_f):        # 判断 i是否是是完全数，注意，加上1 是因为，储存因子的列表不包含1
                l_n.append(i)             # 是完全数，就存起来
            l_f.clear()                    # 这一步很重要，清空储存因子的列表，因为每次判断i是不是完全数都会向该列表添加因子（除非i是质数）
        print(len(l_n))              # 题目要求输出 完全数的个数，即 l_n 列表的长度
    except:
        break

发表于 2022-01-04 09:42:16 回复(0)

Java

丶清水冷月

import java.util.*;
public class Main{
public static boolean isPerfectNumber(int n){
//判断是否为完美数
boolean b = false;
int sum = 0;
for(int i =1;i<n;i++){
if(n%i == 0){
sum = sum+i;
}
}
if(sum == n){
b = true;
}
return b;
}
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
while(sc.hasNext()){
int count = 0;//完美数的数量
int n = sc.nextInt();
for(int i =1;i<=n;i++){
if(isPerfectNumber(i)){
count++;
}
}
System.out.println(count);
}
}
}

发表于 2022-01-03 21:00:09 回复(0)

Java

奥因克

import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while(sc.hasNextInt()){
            int n = sc.nextInt();
            int count = 0;
            for(int i = 1; i <= n;i++){
                if(isPerfect(i)){
                    count++;
                }
            }
            System.out.println(count);
        }
    }
    public static boolean isPerfect(int num){
        int result = 0;
        for(int i = 1; i <= num/2;i++){
            if(num % i==0 && num!=i){
                result += i;
            }
        }
        if(result == num){
            return true;
        }
        return false;
    }
}

发表于 2021-11-30 10:53:50 回复(0)

Java

牛客176747785号

import java.util.*;
public class Main{
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()) {
            int n = sc.nextInt();
            int count = 0;
            for(int i = 2; i <= n; i++) {
                if(isP(i)) count++;
            }
            System.out.println(count);
        }
    }
    public static boolean isP(int n) {
        int sum = 0;
        for(int i = 1; i * i <= n; i++) {
            if(n % i == 0) {
                int k = n / i;
                if(k == i) {
                    sum += i;
                } else {
                    sum += (i + k);
                }
            }
        }
        if(sum == 2 * n) {
            return true;
        } else {
            return false;
        }
    }
}

发表于 2021-10-31 22:30:55 回复(0)

Java

牛客150518786号

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        while (scan.hasNext()) {
            int a = scan.nextInt();
            int count = 0;
            for (int i = 1; i <= a; i++) {
                int sum = 0;
                for (int j = 1; j <= Math.sqrt(i); j++) {
                    if (i % j == 0) {
                        sum += (j + i / j);
                    }
                }
                if (sum == i * 2) {
                    count += 1;
                }
            }
            System.out.println(count - 1);
        }
    }
}

发表于 2021-09-20 23:34:33 回复(0)

豆本

using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace Consoletest1
{
public class MainClass
{
public static void Main()
{
string a = Console.ReadLine();
List<int> kk = new List<int>();
int c = 0;
int he = 0;
int count = 0;
while (a != null)
{
c = Convert.ToInt32(a);
for (int j = 1; j <= c; j++)
{
for (int i = 1; i < j ; i++)
{
if (j % i == 0)
{
he += i;
}
}
if (he == j)
{
count++;
}
he = 0;
}
kk.Add(count);
count = 0;
a = Console.ReadLine();
}
foreach (int s in kk)
{
Console.WriteLine("{0}",s);
}
Console.ReadKey();
}
}
}

发表于 2021-09-08 17:28:49 回复(0)

木析

开一个数组存储真因子的和，从2开始遍历，每遍历到一个数，就把该数的值加入到对应的倍数所在的数组位置，如果数组值（即真因子之和）和下标相同，即表示该下标对应的数是完美数。

#include<iostream>
#include<stdio.h>
#include<string>
#include<vector>
#include<algorithm>
#include<math.h>
using namespace std;
int main()
{
    int n;
    while(cin>>n) {
        vector<int> dp(n+1,1); //每个数都有因子1
        int ans=0;
        for(int i=2;i<=n;++i) {
            if(dp[i]==i)
                ++ans;
            for(int j=i*2;j<=n;j+=i) {
                dp[j]+=i; //i的倍数（即以i为真因子的数）加上i的值
            }
        }
        cout<<ans<<endl;
    }
    return 0;
}

发表于 2021-06-27 16:01:05 回复(0)

牛客939419244号

while True:
    try:
        n = int(input())
        a = {}
        for i in range(1, n+1):
            a[i] = 1
        for i in range(2, int(n**0.5)+1):
            a[i*i] = a[i*i] + i
            for j in range(i+1, n//i+1):
                a[i*j] = a[i*j] + i + j
        sum = 0
        for i in range(2, n+1):
            if a[i] == i:
                sum += 1

        print(sum)

    except:
        break

发表于 2021-06-23 22:54:52 回复(0)

Java

牛客771793137号

import java.util.Scanner;
public class Main {
public static void main(String[] args){
Scanner sc=new Scanner(System.in);
while(sc.hasNext()){
int n=sc.nextInt();
int count=0;
for(int i=1;i<=n;i++)
if(sums(i)==i)count++;
System.out.println(count);
}
}
public static int sums(int n){
int res=0;
for(int i=1;i<=n/2;i++){ //此处开始想用Math.sqrt以节省时间，后来明白，那样做时间节省，结果错误，用n/2刚刚好
if(n%i==0)res+=i;
}
return res;
}
}

编辑于 2021-06-15 11:08:41 回复(0)

Python

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)

上大-黄志栋

这个题貌似没太多简便算法，首先想到的就是遍历，而且很自然想到遍历区间是每个数的开方

def perfectnum(n):
    if n <= 5: return 0
    cnt = 0
    for i in range(6, n+1):
        add = 1
        for j in range(2, int(i**0.5)+1):
            if i%j == 0:
                add = add + j + i//j
        if add == i: cnt += 1
    return cnt
while True:
    try:
        n = int(input())
        print(perfectnum(n))
    except:
        break

发表于 2020-08-26 15:53:52 回复(0)

Python

ShadowAnt_TC

def is_perfect(num):
    yinzi = []
    for i in range(1,num//2+1):
        if num%i==0:
            yinzi.append(i)
    if sum(yinzi)==num:
        return True
    else:
        return False

while True:
    try:
        n = int(input())
        if n<=0 or n>500000:
            print(-1)
            break
        else:
            count_ = 0
            for num in range(2,n+1):
                if is_perfect(num):
                    count_ += 1
            print(count_)
    except:
        break

编辑于 2020-07-29 21:18:15 回复(0)

SHAN_WS

#900ms,还行吧，简单易懂
def pn(n):
    if n < 0&nbs***bsp;n > 500000:
        return -1
    else:
        num = []
        for i in range(1,int(n/2)+1):
            if n % i == 0:
                num.append(i)
        if sum(num) == n:
            return n
        else:
            return -1
while True:
    try:
        n = int(input())
        count = 0
        for i in range(1,n+1):
            if pn(i) == i:
                count += 1
        print(count)
    except:
        break

发表于 2020-07-25 18:40:59 回复(1)

only_boy

#include <iostream>

using namespace std;
//把每一个数n 去一次对1-n/2个数取余，进行判断即可
int main()
{
    int n;
    while(cin>>n)
    {
        int res = 0;
        for(int i = 1;i<=n;i++)
        {
            int tmp = 0;
            for(int j = 1;j<=i/2;j++)
            {
                if(i % j == 0)    tmp+=j;
            }
            if(tmp == i)  res++;
        }
        cout<<res<<endl;
    }

    return 0;
}

发表于 2020-07-13 10:55:18 回复(0)

请叫我昊哥

#include<iostream>
(720)#include<math.h> 
using namespace std;
bool iscount(int n){
	int sum=0;
		for(int i=1;i<n;i++){
			if(n%i==0){
				sum=sum+i;
			}
		}
		if(sum==n){
			return true;
		}else{
			return false;
		}
	

}
int main(){
	int n;
	while(cin>>n){
		int temp=0;
		for(int i=1;i<=n;i++){
			if(iscount(i)){
				temp++;
			}
		}
		cout<<temp<<endl;
	}
}

发表于 2020-04-04 10:06:35 回复(0)