약수 구하기

https://school.programmers.co.kr/learn/courses/30/lessons/136798/solution_groups?language=python3

문제는 위의 링크를 참조 바란다.

def solution(number, limit, power):
    # number 기사의 번호
    # limit 제한
    # 제한이 넘는 애들이 쓰는 무기의 파워
    answer = 0

    buf = []
    for i in range(1, number + 1):
        count = 0
        for e in range(1, int(i ** (1 / 2)) + 1):
            if i % e == 0:
                count += 1
                if e ** 2 != i:
                    count += 1
        buf.append(count)

    for i in buf:
        if limit <= i:
            answer += i
        else:
            answer += power

    return answer

위의 알고리즘에서 가장 중요한 부분은 약수를 찾는 방법이다 루트 N의 시간 복잡도를 가지는 방법은 위의 식과 같다 제곱 근까지만 확인하는 방법으로 제일 좋은방법이다.