숫자 블록

• 문제를 잘 이해한 뒤 다시 정리해보면. begin부터 end까지의 각 수에 대해서, 자기 자신을 제외하고 가장 큰 약수를 찾으라는 문제이다.
  • 정확히는 10,000,000 이하의 가장 큰 약수..
• 어떤 수 n의 가장 큰 약수를 구하려면, 2부터 sqrt(n)까지로 전부 나눠보면 된다. i가 n의 가장 작은 약수라면, 가장 큰 약수는 n/i 이다. sqrt(n)까지 중에 약수가 없다면, n은 소수이다.
  • 즉, n%i == 0 이고, n/i > 10,000,000 인 최소의 i를 찾으면 된다.
    • 2부터 시작해서 저 조건을 만족하는 i가 나올때까지 탐색하는 것보다, n/10,000,000부터 시작해서 탐색하는 것이 약간 더 효율적이긴 하지만, 루프의 전체 반복횟수에 비하면 미미한 차이라서 별 의미 없다
• 이 작업을 m개의 수에 대해서 수행해야 하므로 시간복잡도는 O(m*sqrt(n)) (m⇐10,000, n⇐1,000,000,000)
• 사실, 10,000,000 이하라는 조건만 없다면, 훨씬 더 효율적으로 풀 수 있기는 하다. 2부터 sqrt(n)까지의 모든 수로 나누는 대신 그 범위 안의 모든 소수로 나눠보면 되기 떄문이다
  • 에라토스테네스의 체를 이용해서 x이하의 소수를 모두 찾는데 걸리는 시간은 O(xloglogx)이다
  • x이하의 소수의 개수는 O(logx) 이다.
  • 이 두가지를 적용해보면, 시간 복잡도는 O(sqrt(n)*loglog(sqrt(n)) + m*log(sqrt(n)) = O(sqrt(n)*loglogn + m*logn) 으로 훨씬 단축된다.
  • 그러나.. 10,000,000 이하라는 조건 때문에 이 방법은 불가능.. x가 조건이 없이 그냥 가장 큰 약수라면 n/x가 소수일테지만, x가 10,000,000 이하의 가장 큰 약수라면 n/x는 소수가 아닐 수도 있다.

"""Solution code for "Programmers 12923. 숫자 블록".

- Problem link: https://programmers.co.kr/learn/courses/30/lessons/12923
- Solution link: http://www.teferi.net/ps/problems/programmers/12923
"""

import math


def solution(begin, end):
    answer = []
    for i in range(begin, end + 1):
        if i == 1:
            answer.append(0)
            continue
        for j in range(2, math.isqrt(i) + 1):
            if i % j == 0 and i // j <= 10_000_000:
                answer.append(i // j)
                break
        else:
            answer.append(1)
    return answer