[BOJ/백준] 11653 소인수분해

● [문제번호 11653] 소인수분해

https://www.acmicpc.net/problem/11653

11653번: 소인수분해

 

● 알아야 할 것

: 소인수분해 하는 방법

: 재귀 함수

 

● 풀이 과정

: 소수 목록을 만들어 해당 소수로 나눠지는 지 확인하는 방법도 있지만

직관적으로 2로 계속 나눠보고

안되면 다음 3으로 계속 나눠보고

안되면 다음 4로 나눠보고 하는 방법으로 구현하였다.

 

이렇게 구현해도 괜찮은 이유는

예를 들어 2로 더이상 나눌 수 없을 때 까지 나누면 더이상 2의 배수로 나눌 수 없기 때문이다

 

● 주의 할 것

: 재귀함수의 Base case 고려하기

 

● 참고 할 것

: 소인수분해하는 방법

https://math100.tistory.com/129

 

● 풀이 코드

#include <bits/stdc++.h>

using namespace std;

int N;

// 소인수분해 하는 함수
// 소수 목록을 만든 다음 소인수분해를 해도 되지만
// 예를 들어 2를 계속 나눈 다음에는 2의 배수에서는 나눠지지 않는다
// 따라서 순차적으로 소인수분해를 해도 풀이에 문제되지 않는다
void Factorization(int n, int divide)
{
    // Base case
    // 나눌 수가 없는 경우
    if(n == 1)
        return ;
    
    // 해당 숫자로 나눌 수 있는 동안
    // 출력 + 나누기
    while(n % divide == 0)
    {
        cout << divide << "\n";
        n /= divide;
    }
    
    // 다음 수로 다시 소인수분해
    Factorization(n, divide + 1);
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    // 입력
    cin >> N;
    
    // 소인수분해 호출
    // 2부터 나눠보기
    Factorization(N, 2);
    
    return 0;
}

 

 

● [백준] - [알고리즘 기초 1/2] - [303 - 수학 1 (참고)] 문제집

번호	문제 번호	문제 이름	풀이 링크
1	11005	진법 변환 2	https://pirateturtle.tistory.com/195
2	2745	진법 변환	https://pirateturtle.tistory.com/196
3	11576	Base Conversion	https://pirateturtle.tistory.com/197
4	11653	소인수분해	https://pirateturtle.tistory.com/198