[백준] 약수의 합2

https://www.acmicpc.net/problem/17427

테스트문

start = time.time()
input_ = int(input())
sum(map(lambda x : get_divisor(x), range(1, input_ + 1)))
print(time.time() - start)

첫 번째 풀이

def get_divisor(n):
    total = 0
    j = 1
    while j <= n:
        if n % j == 0:
            total += j
        j += 1
    return total

• 효율성을 고려하지 않은 풀이임
• input이 10000일때 약 5.73초 소요.

두 번째 풀이

def get_divisor(n):
    total = 0
    for j in range(1, int(n**(1/2)) + 1):
        if n % j == 0:
            total += j
            if n // j != j:
                total += n // j
    return total

• n의 제곱근일떄 까지만 구해주고, 제곱근 이상의 크기를 가지면 미리 구한 수의 pair로 구해줌
  ex) 10의 경우, 1, 10, 2, 5 와 같은 순서로 append
• input이 10000일 때, 약 1.77초 소요

우수답안

n = int(input())
print(sum([(n // i) * i for i in range(1, n + 1)]))

• 결국 약수의 성질을 이용한 수학적 개념으로 품.
• 10이라고 치면 10까지는 1이 10번 (1..10), 2가 5번(2,4,6,8,10), 3이 3번 (3,6,9) ... 이런식으로 더해주면됨
• input이 1000000이어도 0.0598초만에 출력