当前位置:首页 > 数论 > 正文
SSOJ1186求完数
173+

题目大意:完数是指因子(不含自己)之和等于他本身的数,请输出n以内所有完数。

题目描述

一个数如果恰好等于它的因子(能被它除尽的数,除本身)之和。比如6,它的因子有1,2,3,并且6=1+2+3,则6是完数。输出n以内所有完数。(n<10000)

输入

一行,一个整数n

输出

输出n以内的所有完数,每个数之间用空格隔开。

样例输入

1000

样例输出

6 28 496

解题思路

暴力解法:对于1到n中的每个数字i,分别枚举他们的约数,如何约数之和等于i,那么就是完数需要输出来。时间复杂度O(n*n)。

一个数的约数是成对存在的,一个不超过√n,另外一个不小于√n。我们只需要枚举小的那个约数,计算大的那个约数就行。需要特别注意的是,1和n这对约数,只加1,不加n;如果是平方数,如25,因子5只加1次。时间复杂度O(n√n)。

程序实现

更多

About

坚决不Copy代码!

本文标签:,,,,,,,,

SSOJ1186求完数:等您坐沙发呢!

发表评论

😉😐😡😈🙂😯🙁🙄😛😳😮mrgreen.png😆💡😀👿😥😎😕

快捷键:Ctrl+Enter