소인수분해

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

개요

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

방법

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

예제

• C

#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은 그냥 숫자만 출력 후 줄 바꿈 해준다.

• 자바(JAVA)

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("*");
                        }
                  }
            }
      }
}

• 파이썬(Python)

에라토스테네스의 체 알고리즘을 활용하였다.

# 소인수분해
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

참고자료

• 〈소인수분해〉, 《나무위키》
• 고수, 〈소인수분해 란??〉, 《네이버 블로그》, 2018-04-05
• Milvus Migrans, 〈(C언어) 소인수분해〉, 《티스토리》, 2012-04-09
• 姫鐘, 〈(JAVA) 소인수 분해(Integer Factorization)〉, 《티스토리》, 2016-09-06
• ratsgo, 〈소인수분해〉, 《github》, 2017-10-07
• 수학방 공식 홈페이지 - https://mathbang.net/200

같이 보기

• 소수
• C
• 자바
• 파이썬
• 합성수
• 자연수
• 소인수
• 거듭제곱
• 알고리즘

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

블록체인 : 블록체인 기술, 합의 알고리즘, 암호 알고리즘 □■⊕, 알고리즘, 블록체인 플랫폼, 블록체인 솔루션, 블록체인 서비스 암호기술 개인키 • 경량암호 • 다자간 계산(MPC) • 다중서명(멀티시그) • 동형암호 • 디지털서명 • 링서명 • 배타적 논리합(XOR) • 복호화 • 블랙박스 암호 • 서명 • 소수 • 소인수분해 • 슈노르서명 • 스케인 • 스키테일 • 스테가노그래피 • 안전한 다자간 계산(SMPC) • 암호 • 암호경제학 • 암호문 • 암호키 • 암호학 • 암호화 • 이산로그 • 전자봉투 • 전자서명 • 전치암호 • 종단간 암호화 • 치환암호(대체암호) • 키 • 패딩 • 패스워드 • 평문 • 합성수 • 해독 • 해시 • 형태보존암호 • 혼돈 • 화이트박스 암호 • 확산 논리연산 논리곱(AND) • 논리연산 • 논리합(OR) • 배타적 논리합(XOR) • 부울곱 • 부울대수 • 부울합 • 부정논리곱(NAND) • 부정논리합(NOR) • 부정연산(NOT) SHA SHA • SHA0 • SHA1 • SHA2 • SHA224 • SHA256 • SHA384 • SHA512 • SHA512/224 • SHA512/256 • SHA3 • SHA3-224 • SHA3-256 • SHA3-384 • SHA3-512 MD MD • MD2 • MD4 • MD5 • RIPEMD • RIPEMD-128 • RIPEMD-160 • RIPEMD-256 • RIPEMD-320 기타 해시 CRC-16 • CRC-32 • CRC-64 • Keccak-256 • Keccak-384 • Keccak-512 • Shake-128 • Shake-256 • 베이스32 • 베이스32 파일 • 베이스58 • 베이스64 • 베이스64 파일 • 순환중복검사 대칭키 AES • ARIA(아리아) • DES • HIGHT(하이트) • LEA • SEED(시드) • 대칭키 • 대칭키 암호 알고리즘 • 디피-헬만 • 디피-헬만 키교환 • 레인달 • 블로피시 • 블록암호 • 스트림 암호 • 에스박스(S-Box) • 트리플 DES 비대칭키 PKI • RSA • 공개키 • 공개키 암호 알고리즘 • 비대칭키 • 엘가말 • 타원곡선 • 타원곡선 디지털서명 알고리즘 • 타원곡선암호 영지식증명 영지식 상호 증명(ZKIP) • 영지식 스나크 • 영지식 스타크 • 영지식증명 양자암호 BB84 프로토콜 • E91 프로토콜 • B92 프로토콜 • 비밀키 오류율 • 안전성 증명 • 양자난수생성기 • 양자내성암호 • 양자암호 • 양자얽힘 • 양자역학 • 양자중첩 • 양자컴퓨터 • 양자키 • 양자키분배 • 양자통신 • 연속 변수 프로토콜 암호해독 기지평문공격(KPA) • 선택암호문공격(CCA) • 선택평문공격(CPA) • 암호공격 • 암호문 단독공격(COA) • 암호해독 암호학 인물 라이언 플레이페어 • 레너드 애들먼 • 로널드 리베스트 • 마틴 헬만 • 블레즈 드 비즈네르 • 아디 샤미르 • 앨런 튜링 • 웨슬리 피터슨 • 찰스 휘트스톤 • 휫필드 디피 위키 : 자동차, 교통, 지역, 지도, 산업, 기업, 단체, 업무, 생활, 쇼핑, 블록체인, 암호화폐, 인공지능, 개발, 인물, 행사, 일반