프로그래머스 lv2 숫자 블록

출처

https://school.programmers.co.kr/learn/courses/30/lessons/12923

풀이

def solution(begin, end):
    answer = []
    
    for block in range(begin, end+1):
        # block이 1이면 1이 못들어가 ㅠ, 0밖에 안됨
        # 왜냐하면 n * 2번째부터 들어가기 때문에
        if block==1:
            answer.append(0)
            continue

        # 왜 int(n**0.5)까지만 약수를 검사해보면 괜찮을까
        # 약수의 성질상 (n**0.5)까지 검사해보면 모든 경우의수에 대해알수 있다.
        # 더 큰수로 나눠볼 필요가 없다. 이미 앞에서 답이 될수 있으면 이미 걸려지기 때문이다.
        # 그래서 1씩 증가시면서 나눠진해가 답이 될수 있으면 바로 반환하면된다.
        # 왜냐하면 가장 빠르게 나눠진게 가장 큰 나눠진해가 나오고 답이 되기 때문이다.
        # 그런데 나눠진해가 10000000 보다 크면 안된다. 블록이 10000000 까지 이기 때문에
        # 그리고 2부터 올려야 한다. 왜냐하면 n * 2번째부터 들어가기 때문에
        # 1부터로 설정하면 n*1번째부터 들어가는거
        case = 1
        for divider in range(2, int(block**0.5)+1):
            if block%divider==0 and block//divider<=10000000:
                case = block//divider
                break
        answer.append(case)
        
    return answer