"소인수분해"의 두 판 사이의 차이
(→예제) |
|||
5번째 줄: | 5번째 줄: | ||
==예제== | ==예제== | ||
− | * [[ | + | * [[C]] |
#include <stdio.h> | #include <stdio.h> | ||
48번째 줄: | 48번째 줄: | ||
코드의 결합도를 낮추고 응집도를 높이기 위해 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> | 코드의 결합도를 낮추고 응집도를 높이기 위해 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> | ||
+ | |||
+ | |||
{{각주}} | {{각주}} | ||
55번째 줄: | 108번째 줄: | ||
* 고수, 〈[https://m.blog.naver.com/PostView.nhn?blogId=extraclasses&logNo=221245845834&proxyReferer=https%3A%2F%2Fwww.google.com%2F 소인수분해 란??]〉, 《네이버 블로그》, 2018-04-05 | * 고수, 〈[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 | * Milvus Migrans, 〈[https://milvus.tistory.com/46 (C언어) 소인수분해]〉, 《티스토리》, 2012-04-09 | ||
+ | * 姫鐘, 〈[https://cbts.tistory.com/95 (JAVA) 소인수 분해(Integer Factorization)]〉, 《티스토리》, 2016-09-06 | ||
==같이 보기== | ==같이 보기== | ||
* [[소수]] | * [[소수]] | ||
+ | * [[C]] | ||
+ | * [[자바]] | ||
{{암호 알고리즘|검토 필요}} | {{암호 알고리즘|검토 필요}} |
2019년 8월 2일 (금) 09:44 판
소인수분해는 합성수를 소수들만의 곱으로 나타내는 것을 말한다.
개요
소수는 1을 제외한 자연수 중에서 약수가 1과 자기 자신밖에 없는 자연수를 말한다. 소인수는 소수의 곱으로 나타낸 수를 말하고 소인수분해는 그 소인수들을 분해해서 소수를 나열한 것이다. 예를 들어, 12의 소인수분해는 으로 분해되고 이것을 정리하여 의 형태로 나타낸다. 결과적으로 소인수분해는 어떠한 수를 소수로 분해하여 곱셈의 형식으로 표기하는 것이다.
예제
#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]
- 자바(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("*"); } } } } }[2]
각주
- ↑ Milvus Migrans, 〈(C언어) 소인수분해〉, 《티스토리》, 2012-04-09
- ↑ 姫鐘, 〈(JAVA) 소인수 분해(Integer Factorization)〉, 《티스토리》, 2016-09-06
참고자료
- 〈소인수분해〉, 《나무위키》
- 고수, 〈소인수분해 란??〉, 《네이버 블로그》, 2018-04-05
- Milvus Migrans, 〈(C언어) 소인수분해〉, 《티스토리》, 2012-04-09
- 姫鐘, 〈(JAVA) 소인수 분해(Integer Factorization)〉, 《티스토리》, 2016-09-06
같이 보기