[include(틀:하위 문서, top1=소인수분해/1~1000)] [include(틀:토론 합의, 토론주소1=FuturisticAllegedScrawnyAdjustment, 합의사항1='소인수분해/1~1000'을 제외한 하위 문서 삭제, 토론주소2=VenomousEagerDysfunctionalNews, 합의사항2=소인수분해의 목록은 1000 이하의 자연수만을 작성하며 '특수한 수' 문단을 삭제한다.)] [include(틀:정수론)] [목차] == 개요 == {{{+1 Prime Factorization · [[素]][[因]][[數]][[分]][[解]]}}} [[합성수]]를 소수들의 곱으로 나타내는 것을 말한다.[* [[합성수]]가 아니어도 상관은 없지만 그럼 아무 의미가 없어진다.] [[소수(수론)|소수]]를 처음 배우는 중학교부터 자주는 아니더라도 계속 쓰이는 기본적인 수학 도구. 모든 합성수가 소인수분해된 형태를 가지고 있다는 것은 [[산술의 기본정리]]로 증명된다. '소인수분해'라는 명칭은 중학교에 가서야 언급되지만, 초등학교 때에도 약수와 배수를 구하기 위해 잠시 사용된다. === 온라인 사이트 === [[http://factordb.com/|factordb]] - 이름 그대로 소인수분해 방법이 알려진 수들의 데이터베이스를 제공한다. 모르는 수의 소인수분해 방법이 궁금할 때 참조하면 좋은 자료. [[울프람알파]]에서도 prime factorization 과 함께 숫자를 넣어주면 소인수분해 결과를 보여준다. 간단히 'factor 숫자' 로도 된다. [[https://www.wolframalpha.com/input/?i=factor+11111111111111111|11111111111111111의 소인수분해]] == 소인수분해를 하는 방법 == 이 문단에서는 1보다 큰 어떤 정수 [math(N)]이 주어졌을 때, [[약수(수학)|약수]]를 찾는 여러 가지 기술에 대해 소개한다. 먼저 가장 쉬운 방법은 아래의 [[배수 판정법]]을 이용하는 것이다. >정수 [math(N)]에 대해서, > 1. 2의 배수[* [[짝수]].]: 끝자리가 짝수.[* 0도 짝수이다.] > 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. 7, 11, 13의 배수: 일의 자리부터 세 자리씩 끊은 뒤, 각 부분을 교대로 빼고 더한 값이 7, 11, 13의 배수.[* 123456789를 예시로 들면, 123-456+789=456이 7의 배수가 아니므로 원래 수는 7의 배수가 아니다. 59255924를 예시로 들면, 59-255+924=728이 7의 배수이므로 원래 수는 7의 배수이다.][* 이 방법은 1001='''7*11*13''', 999999=3^^3^^*37*'''1001''' 임을 이용한 방법이다. 이 외에도 다른 방법들이 있다.][* 11의 배수는 다른 방법으로, 만약 홀수 번째 자리(일의 자리, 백의 자리, 만의 자리... 등)와 짝수 번째 자리(십의 자리, 천의 자리, 십만의 자리... 등)의 각각의 합의 차가 0 또는 11의 배수이면 그 수는 11의 배수이다. (예: 11110 → 1+1+0=2, 1+1=2, 2-2=0 → 11의 배수.)] > 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의 배수인 수.[* 이 방법은 999가 27, 37의 배수인 것을 이용했다.][* 다른 방법(스펜스의 방법)으로는 27의 경우 일의 자리를 8배 하며, 37의 경우 일의 자리 숫자를 11배 하여 나머지 자리 값에서 뺀다 나머지 자리에서 뺀 값이 27/37의 배수이면 원래 수는 27/37의 배수이다.] 또는 아래 정리를 사용할 수도 있다. >모든 [[합성수]]는 그 수의 [[제곱근]]보다 작거나 같은 약수를 갖는다. 증명은 아래와 같다. >[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)]보다 같거나 작다. 이 정리에 의해 어떤 큰 수를 소인수분해 할 때, 그 수의 제곱근 보다 큰 수로 나눌 필요는 없다는 사실을 알 수 있다. 이는 [[노가다(수학)|노가다]]를 통해 소인수분해를 하는 시간을 크게 단축시켜 준다. === [[알고리즘]] === 프로그래밍으로 소인수를 구할 때는 위와 같은 자질구레한 규칙을 따질 필요 없이, 주어진 숫자 n의 소인수를 구한다고 할 경우 아래와 같은 순서로 진행하면 된다. * 1. i=2로 시작하여 i++ 하면서 n%i == 0 인지 체크한다. * 2. n%i==0이 성립하는 경우 i를 소인수로 등록한 후 n은 i로 나눈 값을 저장하고 i는 i++ 하지 않고 i부터 다시 시작하도록 한다. * 3. n이 1이 될 때까지 위 과정을 반복한다. 어차피 작은 소수에서 n%i == 0이 성립하지 못한다면 그보다 큰 합성수는 n%i == 0가 성립하지 못하므로 n%i == 0이 성립하는 첫번째 i는 소수라는 점을 이용한 알고리즘이다. 이 알고리즘으로 소인수를 구하면 천억이 넘는 숫자도 소인수가 순식간에 구해진다. 간단하게 파이썬으로 코딩 해보면 다음과 같다. {{{#!syntax python # -*- coding: utf-8 -*- import os import sys def find_prime(input_num): if input_num <= 2: return [input_num,] for idx in range(2,input_num): if input_num % idx == 0: ret_list = [] val_a = find_prime(idx) val_b = find_prime(int(input_num/idx)) ret_list = val_a + val_b return ret_list return [input_num,] def main(): try: input_num = int(sys.argv[1]) except: print("usage: python main.py <number>") print(" ex> python main.py 12345") quit() prime_list = find_prime(input_num) check_num = 1 for prime_at in prime_list: check_num *= prime_at print("[%s] input_num=%d, check_num=%d" % (input_num == check_num, input_num, check_num)) print("%s" % prime_list) main() }}} 다만 위의 프로그램은 프로그래밍을 익히는 용도로는 유용할수 있으나, 실제 소인수분해 용으로 쓰기에는 적합하지 않다. 실제로 컴퓨터로 다루는 수는 1000억은 '겨우'라는 소리가 나올만큼 큰 수를 다룰 필요가 있기 때문이다. 가장 쉬운 방법은 다른 프로그램을 이용해서 미리 소수 테이블을 작성해 두고, 이를 활용하는 것이다. 예를 들어 2^^16^^ 보다 작은 소수는 6542개인데, 이를 미리 배열에 저장해 두면, 42억 (=2^^32^^ ) 보다 작은 수는 겨우 6542번 나누어 보기만 하면 소수인지 판정하거나, 1개 이상의 소인수를 구할 수 있다. 2^^32^^ 보다 작은 소수는 모두 약 2억개(203,280,221 개) 인데, 이를 미리 구해서 적절한 DB 에 저장해 두면 약 1000경 (= 2^^64^^ = 18,446,744,073,709,551,616) 보다 작은 수의 소인수 분해를 쉽게 할 수 있다. 20 자리 정도 되는 이정도 수면 [[큰 수]]라고 생각할 수 있지만, [[RSA 암호화]]같은 [[암호학]]에서 기본 수백자리 수를 다뤄야 한다. [[https://en.wikipedia.org/wiki/RSA_numbers|RSA 넘버]]를 보면 가장 작은 것이 100자리 부터 시작하는데, 그마저 250자리 수 까지는 모두 소인수분해되었다. 가장 큰 RSA-2048 은 무려 617자리 수이다. 수의 단위 중 이름이 붙은 최고 단위인 [[구골]]이 101자리 수라는 것을 생각해보면, RSA 암호화에서 다루는 수는 사람에게는 어마어마하게 큰 수이다. 밑과 지수를 구하는 기본적인 파이썬 함수는 [[https://futureengineer.tistory.com/49?category=1181513]] 에 설명되어있다. == 관련 문서 == * [[수학]] * [[수학 관련 정보]] * [[소인수]] * [[소수(수론)]] * [[합성수]] * [[인수분해]] * [[산술의 기본정리]] * [[대수학의 기본정리]] * [[소인수분해/목록]] [[분류:소수(수론)]][[분류:산술]][[분류:수학 용어]][[분류:한자어]][[분류: 나무위키 수학 프로젝트]]