검수요청.png검수요청.png

"소인수분해"의 두 판 사이의 차이

위키원
이동: 둘러보기, 검색
 
(사용자 2명의 중간 판 19개는 보이지 않습니다)
1번째 줄: 1번째 줄:
'''소인수분해'''는 [[합성수]]를 [[소수]]들만의 곱으로 나타내는 것을 말한다.
+
'''소인수분해'''<!--소인수 분해-->는 [[합성수]]를 [[소수]]들만의 곱으로 나타내는 것을 말한다.
  
 
==개요==
 
==개요==
소수는 1을 제외한 자연수 중에서 약수가 1과 자기 자신밖에 없는 자연수를 말한다. 소인수는 소수의 곱으로 나타낸 수를 말하고 소인수분해는 그 소인수들을 분해해서 소수를 나열한 것이다. 예를 들어, 12의 소인수분해는 <math>2x2x3</math>으로 분해되고 이것을 정리하여 <math>2^2x3</math>의 형태로 나타낸다.
+
소수는 1을 제외한 [[자연수]] 중에서 [[약수]]가 1과 자기 자신밖에 없는 [[자연수]]를 말한다. [[소인수]]는 [[소수]]의 곱으로 나타낸 수를 말하고 소인수분해는 그 [[소인수]]들을 분해해서 [[소수]]를 나열한 것이다. 예를 들어, 12의 소인수분해는 <math>2\times2\times3</math>으로 분해되고 이것을 정리하여 <math>2^2\times3</math>의 형태로 나타낸다. 결과적으로 소인수분해는 어떠한 수를 [[소수]]로 분해하여 곱셈의 형식으로 표기하는 것이다.
  
{{각주}}  
+
==방법==
 +
# 어떠한 수를 가장 작은 [[소수]]로 나눈다.
 +
# 나누어진 몫이 소수가 될때까지 계속 [[소수로]] 나눈다.
 +
# [[소인수]]로 나타낸다.
 +
# [[거듭제곱]]의 형태로 정리한다.
 +
 
 +
==예제==
 +
* [[C]]
 +
#include <stdio.h>
 +
 
 +
<font color=#006699>void</font> factorization(){
 +
    <font color=#808080>int</font> n;
 +
    <font color=#006699>while</font>(1){
 +
        <font color=#FF1493>printf</font>(<font color=blue>"Input: "</font>);
 +
        <font color=#FF1493>scanf</font>(<font color=blue>"%d"</font>,&n);
 +
 
 +
        <font color=#006699>if</font>(n<2) <font color=#006699>return</font>;
 +
        <font color=#808080>int</font> p=2;
 +
        <font color=#808080>int</font> primes[20];
 +
        <font color=#808080>int</font> index=0;
 +
        <font color=#808080>int</font> i;
 +
 
 +
        <font color=#006699>while</font>(n!=1){
 +
            <font color=#006699>if</font>(n%p==0){
 +
                n=n/p;
 +
                primes[index]=p;
 +
                index++;
 +
                p=2;
 +
            }
 +
            <font color=#006699>else</font>{
 +
                p++;
 +
            }
 +
        }
 +
 
 +
        <font color=#006699>if</font>(index==1) <font color=#FF1493>printf</font>(<font color=blue>"소수\n"</font>);
 +
        <font color=#006699>else</font>{
 +
            <font color=#006699>for</font>(i=0; i<index-1; i++){
 +
                <font color=#FF1493>printf</font>(<font color=blue>"%d*"</font>,primes[i]);
 +
            }
 +
            <font color=#FF1493>printf</font>(<font color=blue>"%d\n"</font>,primes[i]);
 +
        }
 +
    }
 +
}
 +
 +
<font color=#808080>int</font> main(<font color=#006699>void</font>){
 +
    factorization();
 +
    <font color=#006699>return</font> 0;
 +
}
 +
 
 +
코드의 결합도를 낮추고 응집도를 높이기 위해 main() 함수에서는 factorization() 함수를 호출만 가능하도록 하였다. factorization() 함수에서는 일단 처리할 숫자 n을 정수형으로 선언하고 무한루프 안에서 scanf 를 통해 사용자로부터 입력받는다. n이 2보다 작으면 함수를 종료시키고 그게 아니면 필요한 변수들을 선언하기 시작한다. 우선 p는 2로 초기화되는데 이건 숫자 n을 나누어떨어지게 하면 소인수분해의 결과 중 하나가 되는 후보의 역할이다. primes[20]은 소인수분해의 결과를 저장해두기 위한 정수형 배열이고 index는 primes 배열에 인덱스 0부터 차곡차곡 소인수들을 넣기 위한 인덱스 변수이다. 그리고 출력에 사용할 반복용 변수 i 가 있다. 알고리즘은 n이 1이 될때까지 계속 루프를 돌리는데 n을 p로 나눈 나머지가 0이면 p는 소인수가 되므로 p를 primes[]의 적절한 위치에 넣고 index를 1 증가시킨다. 또한 n에는 n을 p로 나눈 값이 다시 할당된다. 그리고 p에 초깃값 2를 다시 할당한 다음 루프의 처음으로 돌아간다. n을 p로 나눈 나머지가 0이 아니면 p는 n의 소인수가 아니므로 p를 1 증가시킨 후 다시 루프의 처음으로 돌아간다. n이 1이 되면 완전히 나누어떨어져 더이상 소인수를 찾을 수 없음으로 소인수분해 찾기는 종료된다. 이때 index가 1이라면 이건 0번 인덱스에 하나의 숫자만 들어갔다는 뜻이 되므로 그 수는 소수라고 할 수 있다. 따라서 소수라고 출력해주고 아니라면 for 문에서 반복용 변수 i를 이용해 결과값을 하나씩 출력해준다. 이때 주의사항은 현재 index라는 값은 실제 유효한 값이 들어 있는 마지막 인덱스보다 1 크다는 것이다. 따라서 primes[] 배열의 인덱스 index-1까지의 값을 출력해줘야 하는데 마지막 값을 출력한 이후에는 index-2 까지 (숫자)<sup>x</sup>를 출력해주고 index-1은 그냥 숫자만 출력 후 줄 바꿈 해준다.<ref>Milvus Migrans, 〈[https://milvus.tistory.com/46 (C언어) 소인수분해]〉, 《티스토리》, 2012-04-09</ref>
 +
 
 +
* [[자바]](JAVA)
 +
<font color=#990085>package</font> jungbo;
 +
 +
<font color=#990085>import</font> java.util.InputMismatchException;
 +
<font color=#990085>import</font> java.util.Scanner;
 +
 +
<font color=#990085>public class</font> T32IntegerFactorization {
 +
      <font color=#990085>public static void</font> main(String[] args) {
 +
            <font color=#990085>int</font> num; ''<font color=green>//수를 입력받을 변수</font>''
 +
            <font color=#990085>int</font> print; ''<font color=green>//출력을 위한 변수</font>''
 +
            Scanner scan = <font color=#990085>new</font> Scanner(System.<font color=#0900FF>in</font>);
 +
            <font color=#990085>while</font>(<font color=#990085>true</font>){
 +
                  <font color=#990085>try</font>{
 +
                        System.<font color=#0900FF>out</font>.print(<font color=#0900FF>"소인수분해 할 수를 입력하세요. : "</font>);
 +
                        num = scan.nextInt();
 +
                        print = num; ''<font color=green>//num은 변하기 때문에 출력을 위해 print에 미리 넣어두었다.</font>''
 +
                        <font color=#990085>break</font>;
 +
                  }<font color=#990085>catch</font>(InputMismatchException ex){
 +
                      System.<font color=#0900FF>out</font>.println(<font color=#0900FF>"숫자만 입력해야 합니다."</font>);
 +
                  }
 +
            }
 +
            scan.close();
 +
 +
            <font color=#990085>int</font> array[] = <font color=#990085>new</font> int[20]; ''<font color=green>//답항을 출력할 변수</font>''
 +
            <font color=#990085>int</font> cnt=0; ''<font color=green>//배열 자리 지정 변수</font>''
 +
            <font color=#990085>int</font> div=2; ''<font color=green>//나누기에 사용할 변수</font>''
 +
 +
            <font color=#990085>if</font>(num>=2){
 +
                <font color=#990085>while</font>(<font color=#990085>true</font>){
 +
                    <font color=#990085>if</font>(num%div==0){
 +
                          array[cnt]=div;
 +
                          cnt++;
 +
                          num=num/div;
 +
                          <font color=#990085>if</font>(num==1)<font color=#990085>break</font>;
 +
                    }<font color=#990085>else</font>{
 +
                          div++;
 +
                    }
 +
                }
 +
            }
 +
            System.<font color=#0900FF>out</font>.print(print+<font color=#0900FF>" = "</font>);
 +
            <font color=#990085>for</font>(cnt=0;cnt<array.<font color=#0900FF>length</font>;cnt++){
 +
                  <font color=#990085>if</font>(array[cnt]!=0){
 +
                        System.<font color=#0900FF>out</font>.print(array[cnt]);
 +
                        <font color=#990085>if</font>(array[cnt+1]!=0){
 +
                        System.<font color=#0900FF>out</font>.print(<font color=#0900FF>"*"</font>);
 +
                        }
 +
                  }
 +
            }
 +
      }
 +
}<ref>姫鐘, 〈[https://cbts.tistory.com/95 (JAVA) 소인수 분해(Integer Factorization)]〉, 《티스토리》, 2016-09-06</ref>
 +
 
 +
* [[파이썬]](Python)
 +
: 에라토스테네스의 체 알고리즘을 활용하였다.
 +
''<font color=green># 소인수분해</font>''
 +
<font color=#006699>def</font> <font color=#cc00ff>get_prime_factors</font>(n):
 +
    ''<font color=green># n 범위 내의 소수를 구한다</font>''
 +
    primelist = primeSieve(n)
 +
    ''<font color=green># 이 소수들 중 n으로 나누어 떨어지는</font>''
 +
    ''<font color=green># 소수를 구하고, 몇 번 나눌 수 있는지 계산</font>''
 +
    ''<font color=green># 예 : n = 8, factors = [(2, 3)]</font>''
 +
    ''<font color=green># 예 : n = 100, fcount = [(2: 2), (5: 2)]</font>''
 +
    factors = []
 +
    <font color=#006699>for</font> p in primelist:
 +
        count = <font color=#ff6600>0</font>
 +
        <font color=#006699>while</font> n % p == <font color=#ff6600>0</font>:
 +
            n /= p
 +
            count += <font color=#ff6600>1</font>
 +
        <font color=#006699>if</font> count > <font color=#ff6600>0</font>:
 +
            factors.append((p, count))
 +
    <font color=#006699>return</font> factors<ref>ratsgo, 〈[https://ratsgo.github.io/data%20structure&algorithm/2017/10/07/prime/ 소인수분해]〉, 《github》, 2017-10-07</ref>
 +
 
 +
{{각주}}
  
 
==참고자료==
 
==참고자료==
 +
* 〈[https://namu.wiki/w/%EC%86%8C%EC%9D%B8%EC%88%98%EB%B6%84%ED%95%B4 소인수분해]〉, 《나무위키》
 +
* 고수, 〈[https://m.blog.naver.com/PostView.nhn?blogId=extraclasses&logNo=221245845834&proxyReferer=https%3A%2F%2Fwww.google.com%2F 소인수분해 란??]〉, 《네이버 블로그》, 2018-04-05
 +
* Milvus Migrans, 〈[https://milvus.tistory.com/46 (C언어) 소인수분해]〉, 《티스토리》, 2012-04-09
 +
* 姫鐘, 〈[https://cbts.tistory.com/95 (JAVA) 소인수 분해(Integer Factorization)]〉, 《티스토리》, 2016-09-06
 +
* ratsgo, 〈[https://ratsgo.github.io/data%20structure&algorithm/2017/10/07/prime/ 소인수분해]〉, 《github》, 2017-10-07
 +
* 수학방 공식 홈페이지 - https://mathbang.net/200
  
 
==같이 보기==
 
==같이 보기==
 +
* [[소수]]
 +
* [[C]]
 +
* [[자바]]
 +
* [[파이썬]]
 +
* [[합성수]]
 +
* [[자연수]]
 +
* [[소인수]]
 +
* [[거듭제곱]]
 +
* [[알고리즘]]
  
{{알고리즘|검토 필요}}
+
{{암호 알고리즘|검토 필요}}

2019년 8월 2일 (금) 17:15 기준 최신판

소인수분해합성수소수들만의 곱으로 나타내는 것을 말한다.

개요[편집]

소수는 1을 제외한 자연수 중에서 약수가 1과 자기 자신밖에 없는 자연수를 말한다. 소인수소수의 곱으로 나타낸 수를 말하고 소인수분해는 그 소인수들을 분해해서 소수를 나열한 것이다. 예를 들어, 12의 소인수분해는 으로 분해되고 이것을 정리하여 의 형태로 나타낸다. 결과적으로 소인수분해는 어떠한 수를 소수로 분해하여 곱셈의 형식으로 표기하는 것이다.

방법[편집]

  1. 어떠한 수를 가장 작은 소수로 나눈다.
  2. 나누어진 몫이 소수가 될때까지 계속 소수로 나눈다.
  3. 소인수로 나타낸다.
  4. 거듭제곱의 형태로 정리한다.

예제[편집]

#include <stdio.h>
 
void factorization(){
    int n;
    while(1){
        printf("Input: ");
        scanf("%d",&n);
 
        if(n<2) return;
        int p=2;
        int primes[20];
        int index=0;
        int i;
 
        while(n!=1){
            if(n%p==0){
                n=n/p;
                primes[index]=p;
                index++;
                p=2;
            }
            else{
                p++;
            }
        }
 
        if(index==1) printf("소수\n");
        else{
            for(i=0; i<index-1; i++){
                printf("%d*",primes[i]);
            }
            printf("%d\n",primes[i]);
        }
    }
}

int main(void){
    factorization();
    return 0;
}

코드의 결합도를 낮추고 응집도를 높이기 위해 main() 함수에서는 factorization() 함수를 호출만 가능하도록 하였다. factorization() 함수에서는 일단 처리할 숫자 n을 정수형으로 선언하고 무한루프 안에서 scanf 를 통해 사용자로부터 입력받는다. n이 2보다 작으면 함수를 종료시키고 그게 아니면 필요한 변수들을 선언하기 시작한다. 우선 p는 2로 초기화되는데 이건 숫자 n을 나누어떨어지게 하면 소인수분해의 결과 중 하나가 되는 후보의 역할이다. primes[20]은 소인수분해의 결과를 저장해두기 위한 정수형 배열이고 index는 primes 배열에 인덱스 0부터 차곡차곡 소인수들을 넣기 위한 인덱스 변수이다. 그리고 출력에 사용할 반복용 변수 i 가 있다. 알고리즘은 n이 1이 될때까지 계속 루프를 돌리는데 n을 p로 나눈 나머지가 0이면 p는 소인수가 되므로 p를 primes[]의 적절한 위치에 넣고 index를 1 증가시킨다. 또한 n에는 n을 p로 나눈 값이 다시 할당된다. 그리고 p에 초깃값 2를 다시 할당한 다음 루프의 처음으로 돌아간다. n을 p로 나눈 나머지가 0이 아니면 p는 n의 소인수가 아니므로 p를 1 증가시킨 후 다시 루프의 처음으로 돌아간다. n이 1이 되면 완전히 나누어떨어져 더이상 소인수를 찾을 수 없음으로 소인수분해 찾기는 종료된다. 이때 index가 1이라면 이건 0번 인덱스에 하나의 숫자만 들어갔다는 뜻이 되므로 그 수는 소수라고 할 수 있다. 따라서 소수라고 출력해주고 아니라면 for 문에서 반복용 변수 i를 이용해 결과값을 하나씩 출력해준다. 이때 주의사항은 현재 index라는 값은 실제 유효한 값이 들어 있는 마지막 인덱스보다 1 크다는 것이다. 따라서 primes[] 배열의 인덱스 index-1까지의 값을 출력해줘야 하는데 마지막 값을 출력한 이후에는 index-2 까지 (숫자)x를 출력해주고 index-1은 그냥 숫자만 출력 후 줄 바꿈 해준다.[1]

package jungbo;

import java.util.InputMismatchException;
import java.util.Scanner;

public class T32IntegerFactorization {
     public static void main(String[] args) {
           int num; //수를 입력받을 변수
           int print; //출력을 위한 변수
           Scanner scan = new Scanner(System.in);
           while(true){
                 try{
                       System.out.print("소인수분해 할 수를 입력하세요. : ");
                       num = scan.nextInt();
                       print = num; //num은 변하기 때문에 출력을 위해 print에 미리 넣어두었다.
                       break;
                 }catch(InputMismatchException ex){
                      System.out.println("숫자만 입력해야 합니다.");
                 }
           }
           scan.close();

           int array[] = new int[20]; //답항을 출력할 변수
           int cnt=0; //배열 자리 지정 변수
           int div=2; //나누기에 사용할 변수

           if(num>=2){
                while(true){
                    if(num%div==0){
                         array[cnt]=div;
                         cnt++;
                         num=num/div;
                         if(num==1)break;
                    }else{
                         div++;
                    }
                }
            }
            System.out.print(print+" = ");
            for(cnt=0;cnt<array.length;cnt++){
                  if(array[cnt]!=0){
                        System.out.print(array[cnt]);
                        if(array[cnt+1]!=0){
                        System.out.print("*");
                        }
                  }
            }
      }
}[2]
에라토스테네스의 체 알고리즘을 활용하였다.
# 소인수분해
def get_prime_factors(n):
    # n 범위 내의 소수를 구한다
    primelist = primeSieve(n)
    # 이 소수들 중 n으로 나누어 떨어지는
    # 소수를 구하고, 몇 번 나눌 수 있는지 계산
    # 예 : n = 8, factors = [(2, 3)]
    # 예 : n = 100, fcount = [(2: 2), (5: 2)]
    factors = []
    for p in primelist:
        count = 0
        while n % p == 0:
            n /= p
            count += 1
        if count > 0:
            factors.append((p, count))
    return factors[3]

각주[편집]

  1. Milvus Migrans, 〈(C언어) 소인수분해〉, 《티스토리》, 2012-04-09
  2. 姫鐘, 〈(JAVA) 소인수 분해(Integer Factorization)〉, 《티스토리》, 2016-09-06
  3. ratsgo, 〈소인수분해〉, 《github》, 2017-10-07

참고자료[편집]

같이 보기[편집]


  검수요청.png검수요청.png 이 소인수분해 문서는 암호 알고리즘에 관한 글로서 검토가 필요합니다. 위키 문서는 누구든지 자유롭게 편집할 수 있습니다. [편집]을 눌러 문서 내용을 검토·수정해 주세요.