기여내역은 언제든 초기화될 수 있으며, 예기치 못한 오류가 발생할 수 있습니다.
소인수분해
덤프버전 :
하위 문서: 소인수분해/1~1000, }}}
1. 개요[편집]
素因數分解 / prime factorization
합성수를 소수[1]들의 곱으로 나타내는 것을 말한다.[2] 소수를 처음 배우는 중학교부터 자주는 아니더라도 계속 쓰이는 기본적인 수학 도구. 모든 합성수가 소인수분해된 형태를 가지고 있다는 것은 산술의 기본정리로 증명된다.
소인수 분해를 직관적으로 설명한 영상
'소인수분해'라는 명칭은 중학교 1학년에 가서야 언급되지만, 초등학교 5학년 때 약수와 배수를 구하기 위해 잠시 사용된다.
1.1. 온라인 사이트[편집]
factordb - 이름 그대로 소인수분해 방법이 알려진 수들의 데이터베이스를 제공한다. 모르는 수의 소인수분해 방법이 궁금할 때 참조하면 좋은 자료.
Calculator Soup®라는 홈페이지에서도 소인수분해가 가능하다.
울프람알파에서도 prime factorization 과 함께 숫자를 넣어주면 소인수분해 결과를 보여준다. 간단히 'factor N'(N은 양의 정수)로도 된다.
11111111111111111의 소인수분해
2. 소인수분해를 하는 방법[편집]
이 문단에서는 1보다 큰 어떤 정수 [math(N)]이 주어졌을 때, 10진법 표기에서 약수를 찾는 여러 가지 기술에 대해 소개한다. 먼저 사람의 입장에서 가장 쉬운 방법은 아래의 배수 판정법을 이용하는 것이다.
보다 일반적으로 n이 합성수이고, 소인수가 2개 이상일 때, n의 배수를 판별하는 방법은 d가 n의 유니타리 약수라고 했을 때 d와 n÷d의 공배수 여야 하므로 이 둘의 배수판정법을 동시에 만족해야 한다는 것이다.정수 [math(N)]에 대해서,
1. 2의 배수[3]
: 일의 자리 숫자가 짝수.[4]1. 3의 배수: 각 자릿수의 합이 3의 배수.
1. 4의 배수: 맨 뒤 두 자리가 00이거나 4의 배수.
1. 5의 배수: 일의 자리가 0이거나 5인 경우.
1. 6의 배수: [math(N)]이 2의 배수이면서 3의 배수.
1. 8의 배수: 맨 뒤 세 자리가 000 또는 8의 배수.
1. 9의 배수: 각 자릿수의 합이 9의 배수.
1. 10의 배수: 일의 자리가 무조건 0.
1. 10n의 배수: 가장 끝의 n개의 자리가 모두 0.
1. 7, 11, 13의 배수: 일의 자리부터 세 자리씩 끊은 뒤, 각 부분을 교대로 빼고 더한 값이 7, 11, 13의 배수.[5]
[6][7]1. 15의 배수: [math(N)]이 5의 배수이면서 3의 배수.
1. 25의 배수: 맨 뒤 두 자리가 00 또는 25의 배수(25, 50, 75)
1. 12의 배수: [math(N)]이 3의 배수이면서 4의 배수.
1. 20의 배수: [math(N)]이 4의 배수이면서 5의 배수.
1. 30의 배수: [math(N)]이 5의 배수이면서 6의 배수.
1. 48의 배수: [math(N)]이 3의 배수이면서 16의 배수.
1. 72의 배수: [math(N)]이 8의 배수이면서 9의 배수.
1. 27, 37의 배수: 일의 자리부터 3자리씩 끊은 뒤 이들을 모두 합한 결과가 27, 37의 배수인 수.[8]
[9]
또는 아래 정리를 사용할 수도 있다.
증명은 아래와 같다.
이 정리에 의해 어떤 큰 수를 소인수분해 할 때, 그 수의 제곱근 보다 큰 수로 나눌 필요는 없다는 사실을 알 수 있다. 이는 노가다를 통해 소인수분해를 하는 시간을 크게 단축시켜 준다.[math(n)]을 합성수라 하자. 그러면 [math(n=ab,\,1<a,b<n)]이다. 만약 [math(a,b)]가 둘 다 [math(\sqrt n)]보다 크다면, [math(n=\sqrt n\sqrt n<ab=n)]이 되어 모순이다. 따라서 [math(a,b)]중 적어도 하나는 [math(\sqrt n)]보다 같거나 작다.
2.1. 알고리즘[편집]
하위 문서 참조.