python基础(完数的判断)

2024-06-29 10:43| 来源: 网络整理| 查看: 265

题目描述：

一个数如果恰好等于不包含它本身所有因子之和，这个数就称为"完数"。例如，6的因子为1、2、3，而6=1+2+3，因此6是"完数"。编程序找出N之内的所有完数，并按下面格式输出其因子

输入格式：

输出格式：

? its factors are ? ? ?

样例输入： 1000 样例输出： 6 its factors are 1 2 3 28 its factors are 1 2 4 7 14 496 its factors are 1 2 4 8 16 31 62 124 248

代码思路：

我的想法是用遍历来求因数，如何在输出。可奈何他的超时了，时间复杂度为o(n**2)

def ys(n): ys_list = [] for i in range(1,int(n/2)+1): if n % i == 0: ys_list.append(i) return ys_list def list_print(ys_list): print(*ys_list,end=' ') print() N = int(input()) for i in range(3,N+1): ys_list = ys(i) sn = sum(ys_list) if sn == i: print(i,'its factors are',end=' ') list_print(ys_list)

想了想决定在找因数（ys()函数)方面动手：

def ys(n): ys_list = [1] c = int(n**0.5) + 1 for j in range(2, c): if n % j == 0: ys_list.append(j) if j != n // j: # 避免重复添加平方根的因子 ys_list.append(n // j) ys_list.sort() return ys_list

从n/2变成了n**2降低了时间复杂度

通过gpt得知了筛选法（Sieve of Eratosthenes）（先求和判断，再求因数）

完全数是满足其所有因子（除了自身）之和等于本身的数。我们可以利用筛选法来排除非完全数，从而减少计算量。

def find_perfect_numbers(N): is_perfect = [False] * (N + 1) for i in range(2, N + 1): if not is_perfect[i]: sum_factors = 1 j = 2 while j * j

【本文地址】

公司简介

联系我们