'약수구하기' 태그의 글 목록

약수를 구하는 것은, 정수론 문제를 풀 때 기본이 되는 연산 중 하나입니다. 우리는 약수를 구하는 알고리즘을 다음과 같은 구현을 생각할 수 있을 겁니다. 이것은 간단합니다. n의 약수를 구할 때, 나누는 수를 1부터 n까지 모두 검사해 봅니다. 만약에 n을 나누는 수 r로 나눴을 때, 나머지가 0이라면, r로 나누어 떨어지는 겁니다. 이것은 올바른 결과를 냅니다. 하지만, 오래 걸립니다. 예를 들어서, n의 값이 10^12만 되어도 아래와 같은 연산을 10^12번 해야 할 겁니다. 10^12번. 상당히 끔찍하지 않나요? 1초에 단순 연산을 10^9회 정도 한다고 한다면, 1000초, 약 20초, 어마무시한 시간이 걸려버립니다. 이 끔찍한 시간을 줄일 수 있는 방법이 없을까요? Lemma 하나 들고 옵시다..