나눗셈 시도법
나눗셈 시도법, 나눗셈 시도 방법 또는 트라이얼 디비전(trial division)은 정수 소인수분해 알고리즘 중에서 가장 힘들지만 이해하기 가장 쉽다. 나눗셈 시도법 테스트의 기본 개념은 인수분해할 정수인 정수 n이 n의 제곱근보다 작은 각 숫자로 나뉠 수 있는지 확인하는 것이다.
예를 들어, n = 70의 소인수를 찾으려면 70을 연속된 소수로 나누어야 한다. 첫째, 70 / 2 = 35; 다음으로, 2도 3도 35를 균등하게 나누지 않는다. 마지막으로 35/5 = 7이고 7 자체가 소수이다. 따라서 70 = 2 × 5 × 7이다.
나눗셈 시도법은 레오나르도 피보나치가 그의 저서 리베르 아바치(1202)에서 처음으로 설명했다.[1]
각주
[편집]- ↑ Mollin, Richard A. (2002). “A brief history of factoring and primality testing B. C. (before computers)”. 《Mathematics Magazine》 75 (1): 18–29. doi:10.2307/3219180. JSTOR 3219180. MR 2107288.
출처
[편집]- Childs, Lindsay N. (2009). 《A concrete introduction to higher algebra》 3판. Undergraduate Texts in Mathematics. New York, NY: Springer-Verlag. ISBN 978-0-387-74527-5. Zbl 1165.00002.
- Crandall, Richard; Pomerance, Carl (2005). 《Prime numbers. A computational perspective》 2판. New York, NY: Springer-Verlag. ISBN 0-387-25282-7. Zbl 1088.11001.
외부 링크
[편집]- Wikiversity offers a lesson on prime factorization using trial division with Python.
- Fast JavaScript Prime Factor Calculator using trial division. Can handle numbers up to about 253
- Trial Division in Java, C and JavaScript (포르투갈어)