소인수 구하기

소인수는 어떤 수의 약수 중에서 소수인 수를 말함. 

ex) 12의 약수는 1,2,3,4,6,12가 있음. 이중 소수는 2와 3이 있음. 

 

약수는 어떤수가 피제수일 때,  어떤 수를 나누어 떨어지게 만드는 제수를 말함 

소수는 1과 자기 자신 만으로 나누어 떨어지는 수를 말함. 

소인수는 약수 중 소수인 수를 말함. 

cf) 인수는 어떤수를 곱 형태로 '인수 x 인수'로 나타낼 수 있음. 

 

1) 생각해보면 어떤 수의 '인수x인수'에서 앞서 두 인수가 동시에 어떤 수의 제곱근을 초과할 수 없음. 

ex) 36 의 제곱근은 6이고, 6 x 6 형태로 인수로 나타낼 수 있고, 3 x 12 로 나타내거나 1 x 36 이 되어 버리면 한쪽의 인수가 제곱근을 초과해 버리게 됨. 위 1)을 위배하게 됨. 

 

어차피 소인수는 1과 자기 자신을 제외한 약수 중에서도 그러니까 {2부터 ~ 자기 자신의 제곱근 이하의 수} 의 범위에서만 존재할 수 있음. 

 

아래 e는 제곱근에서 소수점 이하의 수를 버리고, 정수의 값만을 취해서 ..

 

 

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

int main() { 
    int b, c, d, e, mok, nmg;
    int a[100];
    scanf("%d", &b);
    c = -1;
    d = 2; 
    while(1) {
                e = (int)sqrt(b);
                while(1){
                            if(d>e) {
                                        d = b; break;
                            }
                            mok = b/d;
                            nmg = b -mok*d;
                            if(nmg == 0)
                                    break;
                            else
                                    d++;
                            }
                c++;
                a[c] = d;
                if (b == d)
                        break;
                b = mok; 
    }
   for(int i = 0; i <=c; i++)
          printf("%d ", a[i]);  
}

20
2 2 5 

 

풀이 

몫을 계속 나누어서 제수로 소인수를 구하는 방식임. 

 

 

1) 소인수를 구할 수를 입력받고, 그 수를 나눌 피제수를 2부터 '정수화(소수인수를 구할 값의 제곱근)' 까지 증가시켜서 나누어 0으로 떨어지면, 그 수를 소인수 배열에 저장함.

2) 몫을 피제수로 저장해서 다시 나누어 위의 작업을 반복하는데, 0으로 나누어 떨어지지 않으면, 제수를 1 증가시켜서 반복함. 

 

ex) 

20/2 = 10 ( 0으로 나누어 떨어져서 제수가 소인수) 

10/2 = 5 (0으로 나누어 떨어져서 제수가 소인수)  

5/2 =! 0  이라서 2를 1씩 증가시켜(d++) '정수화(소수인수를 구할 값의 제곱근)' 보다 커져서 피제수 5 자체가 소인수 

 

 

https://mathbang.net/200#gsc.tab=0

소인수분해, 소인수분해 하는 법, 소인수 뜻

 

순서대로 설명 

1. 20을 넣는다.
2. 2의 제곱근은 4.xxx, 정수값은 4 
3. 2> 4 는 거짓이다. 
4. mok = 10, 
5. nmg = 0 
6. c를 1 증가시켜 a[0] = 2 저장 
7. 20 =! 2 이므로, b 에 몫 10을 저장 후 반복하기 위해 위로 올라감 
8. 피제수는 10이므로 루트 10의 정수화는 e= 3
9. 2 > 3 은 거짓임. 
10. 10 > 2 = 5, mok = 5
11. 10 -2*5 = 0, nmg = 0
12. 반복문을 빠져나와 c를 1 증가시키고, a[1] = 2 저장 
13. 5 =! 2 이므로 mok 5를 b 에 저장 후 위로 올라감 
14. 피제수는 5 이므로 루트 5의 정수화는 e = 2
15. 2 > 2 는 거짓이므로 
16. 5/2 로 mok는 2 
17. nmg = 1 
18. nmg =! 0 이므로 d++ 로 1을 증가시키고 반복문으로 위로 올라감 
19. 3 > 2 이므로 if 조건문은 참 . b가 5인데, d = b를 넣고 안쪽 반복문 빠져나감. 
20. c를 1 증가시키고, a[2]에 5 저장 
21. b 가 5, d가 5 이므로 조건문이 참이므로 바깥쪽 반복문 빠져나감 
22. a[0]~ a[2]까지 차례로 출력