소인수분해 · GCD · LCM

양의 정수를 하나나 둘 넣으십시오. 각각에 대해 p^e × q^f 형태의 소인수분해, 모든 약수, 그 수가 소수인지를 보여 줍니다. 둘 다 넣으면 최대공약수(분수 약분에 쓰입니다)와 최소공배수(공통 주기를 찾을 때 쓰입니다)도 나옵니다. √n까지의 시행 나눗셈은 약 10의 12제곱까지의 수에 충분히 빠르며 전부 브라우저에서 돕니다.

시행 나눗셈을 가망 없는 일이 아니라 실용적인 것으로 만드는 것이 제곱근 한계입니다. 합성수는 언제나 제곱근 이하에 약수를 하나 갖고 있으므로, 시행이 √n을 지나도록 걸리는 것이 없으면 그 수는 소수이고 더 확인할 것이 없습니다. 이것이 1조 개 후보 탐색을 100만 개 탐색으로 바꿔 주고, 브라우저는 그것을 순식간에 해냅니다.

그래도 제곱근에 비례해 늘어나며, 그것이 천장입니다. 자릿수가 두 개 늘 때마다 일이 열 배가 되므로, 스무 자리 수는 100억 번의 시행이 필요하고 암호학적 크기의 수는 상상할 수 없는 차이로 손이 닿지 않습니다. 그 간극은 구현 세부가 아니라 RSA가 작동하는 이유입니다. 2048비트 모듈러스를 인수분해하기 어려운 것은 이 툴이 열두 자리에서 멈추는 것과 같은 산술적 이유 때문입니다.

약수 목록은 수의 크기가 아니라 지수에서 자랍니다. 각 지수에 1을 더해 모두 곱하면 개수가 나옵니다. 1024는 2의 10제곱이라 약수가 열한 개이고, 840은 훨씬 작지만 서른두 개입니다. 작은 소인수를 많이 가진 수는 긴 목록을 만들고, 소수는 두 개를 만듭니다.

최대공약수와 최소공배수는 둘의 곱이 두 입력의 곱과 같다는 항등식으로 묶여 있습니다. 알아 둘 값어치가 있는 이유는, 두 입력이 넉넉한 크기여도 큰 수 둘의 최소공배수는 넘칠 수 있다는 뜻이기 때문입니다. 999999937과 999999893은 둘 다 소수라서 최소공배수가 그 곱이고, 배정밀도가 정확히 표현할 수 있는 가장 큰 정수를 한참 넘어섭니다.