위키원
"소인수분해"의 두 판 사이의 차이
| 2번째 줄: | 2번째 줄: | ||
==개요== | ==개요== | ||
| − | 소수는 1을 제외한 자연수 중에서 | + | 소수는 1을 제외한 [[자연수]] 중에서 [[약수]]가 1과 자기 자신밖에 없는 [[자연수]]를 말한다. [[소인수]]는 [[소수]]의 곱으로 나타낸 수를 말하고 소인수분해는 그 [[소인수]]들을 분해해서 [[소수]]를 나열한 것이다. 예를 들어, 12의 소인수분해는 <math>2\times2\times3</math>으로 분해되고 이것을 정리하여 <math>2^2\times3</math>의 형태로 나타낸다. 결과적으로 소인수분해는 어떠한 수를 [[소수]]로 분해하여 곱셈의 형식으로 표기하는 것이다. |
==방법== | ==방법== | ||
| − | # 어떠한 수를 가장 작은 | + | # 어떠한 수를 가장 작은 [[소수]]로 나눈다. |
| − | # 나누어진 몫이 소수가 될때까지 계속 소수로 나눈다. | + | # 나누어진 몫이 소수가 될때까지 계속 [[소수로]] 나눈다. |
| − | # | + | # [[소인수]]로 나타낸다. |
| − | # | + | # [[거듭제곱]]의 형태로 정리한다. |
==예제== | ==예제== | ||
| 142번째 줄: | 142번째 줄: | ||
* [[파이썬]] | * [[파이썬]] | ||
* [[합성수]] | * [[합성수]] | ||
| + | * [[자연수]] | ||
| + | * [[소인수]] | ||
| + | * [[거듭제곱]] | ||
| + | * [[알고리즘]] | ||
{{암호 알고리즘|검토 필요}} | {{암호 알고리즘|검토 필요}} | ||
2019년 8월 2일 (금) 17:15 기준 최신판
소인수분해는 합성수를 소수들만의 곱으로 나타내는 것을 말한다.
개요[편집]
소수는 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]
- 파이썬(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[3]
각주[편집]
- ↑ Milvus Migrans, 〈(C언어) 소인수분해〉, 《티스토리》, 2012-04-09
- ↑ 姫鐘, 〈(JAVA) 소인수 분해(Integer Factorization)〉, 《티스토리》, 2016-09-06
- ↑ ratsgo, 〈소인수분해〉, 《github》, 2017-10-07
참고자료[편집]
- 〈소인수분해〉, 《나무위키》
- 고수, 〈소인수분해 란??〉, 《네이버 블로그》, 2018-04-05
- Milvus Migrans, 〈(C언어) 소인수분해〉, 《티스토리》, 2012-04-09
- 姫鐘, 〈(JAVA) 소인수 분해(Integer Factorization)〉, 《티스토리》, 2016-09-06
- ratsgo, 〈소인수분해〉, 《github》, 2017-10-07
- 수학방 공식 홈페이지 - https://mathbang.net/200
같이 보기[편집]
