(구)KMS06 : C언어 소인수분해 프로그램 + source (MSFIP)

KMS06 - fasctorization

이 글은 기존의 네이버 블로그에  2019. 1. 31. 11:10에 올라온 게시물입니다.

 

안녕하세요 tomskang입니다.

오늘은 간단하게 소인수 분해 프로그램을 한번 만들습니다.

시간 복잡도는 O(sqrt(N)) 입니다.

바로 소스코드 보겠습니다.

---

소스코드

source.cpp

#include <stdio.h>
#include <math.h>

int main(void) {
	unsigned long long inum, tnum;
	unsigned long long i;
	printf("number : ");
	scanf("%llu", &inum);
	tnum = inum;

	printf("%llu = ", inum);
	for (i = 2; i <= floor(sqrt(inum)); i++) {
		if (!(tnum % i)) {
			tnum /= i;
			printf("%llu  ", i);
			i--;
		}
	}
	if (tnum != 1) {
		printf("%llu\n", tnum);
	}
	else {
		printf("\n");
	}
	return 0;
}

입력 : 소인수분해할 숫자를 하나 입력

출력 : 소인수 분해의 결과를 출력

---

원리

이 프로그램에서는 소인수 분해를 하면서 소수를 찾지도 않고 소인수도 sqrt(N)까지만 찾았는데요, 그럼에도 이 프로그램은 정상작동을 합니다. 중요한 건 아니지만 이유를 적어보면

우선 소수를 찾지 않고서 소인수분해가 가능한 이유는 인수를 2부터 sqrt(N)까지 차례대로 찾기 때문인데요, 합성수도 소인수 분해를 할 수 있기 때문에, 합성수 = 합성수의 인자 * 합성수의 인자로 나타낼 수 있습니다. 합성수의 인자는 합성수보다 작기 때문에 우리가 for 문에서 합성수로 tnum이 나누어지는지를 확인하기 전에, 합성수보다 작은 수로 tnum이 나누어지지 이미 확인해서 나누었기 때문에, 합성수가 tnum으로 나누어지는지 확인할 때면 합성수의 인자인 합성수보다 작은 수가 이미 tnum의 인자가 아니기 때문에 합성수로는 tnum이 나누어질 수가 없게 됩니다. 그리고 합성수의 인자인 수가 합성수인 때도 같은 방법으로 나누어질 수 없고, 그 합성수의 인자가 합성수일 때도 같은 방법으로 나누어질 수가 없고... 가 반복되어서 결국에는 소수로만 나누어지게 되고, i가 합성수일 때는 tnum이 나누어지지 않게 됩니다. 물론, 효율을 극한으로 올리려면 const long long 배열을 만들어서 소수를 저장해 놓거나, 파일에 소수를 적은 다음, fgets로 소수를 저장한 다음 !(tnum % i)를 !(tnum % primearr[i])로 바꾸면 시간 복잡도가 폭발적으로 줄어들게 됩니다.(숫자가 커질수록 소수의 빈도가 줄어들기 때문에 소수를 알아내면 수가 클수록 계산 빈도가 몇십 배쯤 줄어듭니다.) 그러나, 이 프로그램에서 배열에다가 일일이 몇십 자리의 소수를 전부 입력해줄 수도 없고, 소수 탐색이 시간이 오히려 더 많이 걸리기 때문에, 이런 방법을 썼습니다.

인수를 sqrt(N)까지만 찾는 이유는 간단합니다. 바로 sqrt(N)까지 소인수를 다 찼고 나면, 남는 수는 항상 1이거나 소수이기 때문입니다. 모든 자연수 N은 sqrt(N)보다 작은 약수 중 가장 큰 수와 sqrt(N)보다 큰 약수 중 가장 작은 수, N이 제곱수일 경우 sqrt(N)^2로 나타낼 수 있는데, 여기서 제곱수일 경우는 sqrt(N)의 내림(floor 함수)까지 계산하면 소인수 분해가 다 되니 제외하고, 어떤 인의의 숫자 N(이하 N)은 sqrt(N)보다 작은 소인수로 다 나누고 나면 소수가 남을까요?

먼저, 위 과정을 시행하고 남은 수가 합성수라고 생각해 봅시다, 그렇다면 남은 합성수 K도 자연수이기 때문에 sqrt(K)보다 작은 수와 sqrt(K)보다 큰 수로 나누어집니다. 그리고 sqrt(K)보다 작은 수는 sqrt(N)보다 작은 수입니다.(K가 sqrt(N)에서 sqrt(N)을 넘는 N의 약수 중 가장 작은 수이기 때문에 K의 인수에서 그 인수, 또는 K/그 인수는 항상 sqrt(N)보다 작습니다.) 그런데 이미 sqrt(N)보다 작은 수는 이미 tnum의 인수가 아니기 때문에 K는 합성수일 수가 없습니다. 따라서 K가 합성수 일수가 없기 때문에 K는 항상 소수 또는 1입니다.

 

<참고 자료>

검은 그래프 - y = sqrt(N), x = sqrt(N)

빨간 그래프 - y = N/x

교점 P(sqrt(N), sqrt(N))

*빨간 그래프 위의 점 중(파란 점) x, y가 모두 sqrt(N)을 넘어가는 지점이 없다

​

이 원리로 for 문안에서 sqrt(N)보다 작은 소인수를 모두 찼고, for 문을 탈출하고 남은 tnum은 1 또는 sqrt(N)보다 큰 소인수이기 때문에 따로 출력해주시면 됩니다.

 

---

실행 결과

MSFIP(factorization into primes, made by tomskang)

입력형식 : 양의 정수 하나 입력

출력 : 소인수분해 결과 출력

입력 : 12

출력 : 2*2*3(2^2 * 3)

입력 : 24000

출력 : 2*2*2*2*2*2*3*5*5*5(2^6 * 3 * 5^3)

입력 : 193628256549254(193조 6282억 5654만 9254)

출력 : 2*53*53*25349*1359647(2 * 53^2 * 25349 * 1359647)

입력 : 91637482759273672(9경 1637조 4827억 5927만 3672)

출력 : 2*2*2*13*17*31*89*199*523*180503(2^3 * 13 * 17 * 31 * 89 * 199 * 523 * 180503)

 

이상으로 tomskang의 C 프로그래밍 - 소인수분해 프로그램을 마칩니다.

---

relation content

C언어 분수 계산기 MSNCCL (콘솔)

KMS05 : C언어 분수 계산기 MSNCCL fraction (KMS number calculator)