어떤 수를 소수의 곱으로만 나타내는 것을 소인수분해라 하고,
이 소수들을 그 수의 소인수라고 합니다.
예를 들면 13195의 소인수는 5, 7, 13, 29 입니다.
600851475143의 소인수 중에서 가장 큰 수를 구하세요.
먼저 자료형을 맞춰주기 위해 long long int 를 사용해야한다.
서식문자는 %lld 로 받는다.
소인수를 구하는 알고리즘은 책에 다양한 예제가 소개되어있다.
반드시 이해하고 넘어가도록 하자.
#include <stdio.h>
void func() {
long long int num;
while (1) {
printf("Input: ");
scanf("%lld", &num);
if (num<2)
return;
int a = 2;
int array[100];
int ind = 0;
int i;
while (num != 1) {
if (num%a == 0) {
num = num / a;
array[ind] = a;
ind++;
a = 2;
}
else
a++;
}
if (ind == 1) printf("소수\n");
else {
for (i = 0; i<ind - 1; i++) {
printf("%d*", array[i]);
}
printf("%d\n", array[i]);
}
}
}
int main(void) {
func();
return 0;
}