C 언어 예제, 소인수분해 하기

목표는 이렇게 만드는 것이다.

#include <stdio.h>

int main()

{

int i,n;

printf("소인수분해 하고싶은 수를 입력하세요 \n");

scanf("%d", &n);

printf("%d 를 입력하셨습니다. \n",n);

printf("%d = ",n);

for(i=2;i<=n;i++)

{

if(n % i == 0)

{

printf("%d ",i);

n = n / i;

if(n % i == 0)

{

printf("* ");

}

else if(n % i != 0)

{

if(n > i)

printf("* ");

}

i = 1;

}

}

printf("\n");

return 0;

}

찬찬히 뜯어보자.

#include <stdio.h>

int main()

{

int i,n;

printf("소인수분해 하고싶은 수를 입력하세요 \n");

scanf("%d", &n);

printf("%d 를 입력하셨습니다. \n",n);

printf("%d = ",n);

for(i=2;i<=n;i++)

i=2 부터 시작하는 이유는 i=1 부터 시작하면 1 만 매우 많이 11111 뜨는 것을 보게 되기 때문이다. 또한 소인수분해 이므로 소수인 인수를 찾고자 하는 수 n 보다 큰 값으로 나눌 이유는 없다.

{

if(n % i == 0)

{

printf("%d ",i);

n = n / i;

n 을 i 로 나눈 나머지가 0 이면 어쩃든 인수는 인수라는 뜻이 아닌가. 다만 여기서는 i 를 작은 수부터 시작했으므로, 설령 4로 나눠지는 16 같은 수라고 하더라도, 2로 나눌 여지는 모두 제거되어 있다. 따라서 나눠서 나머지가 0이면 출력 하는 것이 가능하다.

if(n % i == 0)

{

printf("* ");

}

또한 나머지가 0 인 경우, 이는 뒤에 다른 소인수가 계속해서 나오며 식이 진행된다는 뜻이 된다. 그러니까 그 수 뒤에 * 를 넣어서 깔끔한 모양이 되게 해 준다.

else if(n % i != 0)

{

if(n > i)

printf("* ");

}

다만 이렇게 했을 시의 문제는, 소인수가 바뀌는 지점에서는 "*" 표시가 나오지 않는다는 점이다. 타당하다. 예를 들어 100 을 생각해보자. 원하는 식은 2*2*5*5 일 것이다. 그런데 여기서, 2 로 두번 나누고 나면 남는 것은 25 로 2로 나눴을 때 나머지가 1 이 된다. 따라서 이 부분이 없다면 식은 2*2 5*5 이렇게 나오게 된다.

여기서 착안한 것은, 이렇게 아직 연산이 끝나지 않은 상태에서는, 나눠야 할 수인 n 값이 아직은 i 보다 크다는 점이다. 만약 소인수분해가 모두 끝나는 시점이라면, 남아 있는 수는 마지막 소인수와 같은 수일 것이다. 예를 들면, 100 에서 2*2*5 를 뺴면 5만 딸랑 남아 있는 것과 같이. 그러므로 n>i 일 때만 "*" 을 출력하라는 코드를 추가로 넣어주면, 숫자가 바뀔 때에도 * 이 출력되도록 할 수 있다. 

i = 1;

i 는 1로 되돌아간다. 만약에 이 부분이 없을 경우, 100 을 입력했을 시에 2가 한 번밖에 나오지 않는다. 왜? 어쨌든 나눠서 나머지가 0 이고 그것을 알았으니 그냥 넘어가고 마는 것이다. 이렇게 하면 모든 소인수가 한번씩만 나오고 끝나게 된다. 그것은 바라는 바가 아니다. 그러니 연산을 초기로 되돌린다. 그런데, i = 2; 는 안 되는 것일까? 불가하다. i=2 로 갈 경우, for 문 조건의 i++ 에 의해 다음번 i 는 3부터 시작하게 된다. 그러면 짝수 n 일 경우, 나눌 수 있는 횟수에는 상관 없이 2로는 한 번만 나눠보고 바로 3으로 넘어가게 되기 때문이다.

}

}

printf("\n");

return 0;

}