완전수 구하기

자기 자신을 제외한 모든 양의 약수들의 합이 자기 자신이 되는 자연수를 완전수라고 한다. 예를 들면, 6과 28은 완전수이다. 6=1+2+3 // 1,2,3은 각각 6의 약수 28=1+2+4+7+14 // 1,2,4,7,14는 각각 28의 약수

입력으로 자연수 N을 받고, 출력으로 N 이하의 모든 완전수를 출력하는 코드를 작성하라.

※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

13개의 풀이가 있습니다. 1 / 2 Page

파이썬 3로 짧게 구현해봤습니다.

num= int(input("숫자를 입력하시오 : "))
print([x for x in range(1, num+1) if x==sum(y for y in range(1, x) if x%y==0)])
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.
# pnumber.py

n = int(input("자연수 입력 > "))
result = 0

for i in range(1,n+1):

    for j in range(1,i):
        if i%j==0:
            result += j
    if result == i:
        print("%d "%(result),end=' ')
    result = 0
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

파이썬3입니다. 박시우님 답을 보니 제가 너무 복잡하게 풀었네요~ㅠㅠ

num = int(input('자연수를 입력하시오: '))
print([sum(i[0:-1]) for i in [[ z for z in range(1, y+1) if y % z ==0 ] for y in [ x for x in range(1,num+1) ]] if sum(i[0:-1]) == i[-1]])
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.
a = int(input('자연수를 입력하세요: '))

result = []
for i in range(a):
    if(a % (i+1) == 0):
        if(i+1 != a):
            result.append(i+1)

print(result)
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.
#-*- coding: utf-8 -*-

#1 부터 n 까지
#n 값이 커질수록 좀 오래걸립니다..


#풀이방법 1  평범함
n =1000
result =  [ c for c in xrange(1, n) if sum(x for x in xrange(1,c) if not c%x) == c]



#풀이방법 2 필터와 람다를 써보자(뭔가 아름다워보임!! 지림)
n =1000
#하하핫 죄송하지만 1번보다 이게 더 빠르다구욧!
beyond_if = list(filter(lambda c: sum(x for x in xrange(1,c) if not c%x) == c,range(1,n)))



#풀이방법 3  윗 방법들의 뼈대입니다 . 풀이방법 3을 코드리뷰해서 풀이방법 1,2를 만들었습니다 :P
n =1000
for c in xrange(1, n):
    if sum(x for x in xrange(1,c) if not c%x) == c:
       print c

※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

Python



def getNature(num):
    yakList = []
    yakSum = 0
    natureList = []
    for x in range(1,num+1):
        for y in range(1,x):
            if x % y == 0:
                yakList.append(y)
        #print x,yakList
        if yakList: yakSum = reduce(lambda a,b: a+b, yakList)
        if yakSum == x: natureList.append(x)
        yakList =[]
        yakSum = 0
    print natureList

※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

#복잡도 때문에 와일문쓰면 겁나게 느려지네요 ㅋ ㅋ ㅋ
#대충 로직만 이렇게 싸지르고 갑니다 ㅋ ㅋ ㅋ

#base and pick number
picker,base = 100,10000

**logic = [ n for n in range(base) if str(n) == str(n)[::-1]]
**print logic[picker - 1]


※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

단순히 N이하의 완전수를 구하기 위해 계산하면 N x N번의 계산을 수행해야 하기 때문에 계산량이 기하급수적으로 늘어납니다. 약수 알고리즘에 대해 조금더 알아보면 최적화를 할수 있는 부분이 있어 이를 토대로 구현해봤습니다.

  1. 하나의 약수를 알면 나머지 다른 약수도 자동으로 알수있다. 예를들어 2는 6의 약수이며 6 / 2는 3이므로 3은 6의 약수임을 알수있다.
  2. 1번의 사실에 근거하면 N의 약수를 구하기 위해 floor(sqrt(N))번의 검사만 수행하면 된다.
from math import *

def isPerfectNumber(n):
    divisors = [1, ]
    for i in range(2, floor(sqrt(n)) + 1):
        if n % i == 0:
            divisors.append(i)
            divisors.append(int(n / i))
    return sum(divisors) == n

def main():
    perfectNumbers = []
    N = int(input("Input Number : "))    
    for i in range(1, N+1):
        if isPerfectNumber(i):
            perfectNumbers.append(i)
    if perfectNumbers:
        print("PerfectNumber :", perfectNumbers)

if __name__ == '__main__':
    main()

실행결과

Input Number : 3000
PerfectNumber : [1, 6, 28, 496]
오 그렇네요. 저도 제곱근을 사용한 방법으로 수정해보겠습니다. - 박 시우, 2016/12/30 04:33 M D
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.
num = int(input("자연수 N을 입력하세요 : "))
if num < 0:
    num = num * -1
i = 1

while i <= num:
    j = 1
    perfect_number = 0
    while j < i:
        if i % j == 0:
            perfect_number += j
        j = j + 1
    if perfect_number == i:
        print("완전수 : ", i)
    i = i + 1

※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.
#-*- coding:utf-8 -*-

def perpect_number(number):
    for i in range(1, number + 1):
        sum = 0
        for j in range(1, i):
            if i % j == 0:
                sum += j
        if(i == sum):
            print '완전수: {}'. format(sum)


perpect_num = int(raw_input('N이하의 모든 완전수 : '))
perpect_number(perpect_num)

※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

풀이 작성

※ 풀이작성 안내
  • 본문에 코드를 삽입할 경우 에디터 우측 상단의 "코드삽입" 버튼을 이용 해 주세요.
  • 마크다운 문법으로 본문을 작성 해 주세요.
  • 풀이를 읽는 사람들을 위하여 풀이에 대한 설명도 부탁드려요. (아이디어나 사용한 알고리즘 또는 참고한 자료등)
  • 작성한 풀이는 다른 사람(빨간띠 이상)에 의해서 내용이 개선될 수 있습니다.
목록으로
코딩도장

코딩도장은 프로그래밍 문제풀이를 통해서 코딩 실력을 수련(Practice)하는 곳입니다.


언어별 풀이 현황
전 체 x 33
java x 4
scala x 1
python x 13
javascript x 1
기 타 x 4
matlab x 1
cpp x 8
ruby x 1