간단한 소인수분해 C++(SW Expert Academy)

난이도 : D2

문제번호 : 1945

※ 저의 풀이가 무조건적인 정답은 아닙니다.

다른 코드가 좀더 효율적이고 좋을 수 있습니다.

다른사람들의 풀이는 언제나 참고만 하시기 바랍니다.

문제 주소 및 출처입니다.

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5Pl0Q6ANQDFAUq&categoryId=AV5Pl0Q6ANQDFAUq&categoryType=CODE

SW Expert Academy

---

목차

1. 문제 설명

2. 문제 해석

3. 소스 코드

---

1. 문제 설명

숫자 N은 아래와 같다. N=2a x 3b x 5c x 7d x 11e N이 주어질 때 a, b, c, d, e 를 출력하라.

제약사항

N은 2 이상 10,000,000 이하이다.

입력

가장 첫 줄에는 테스트 케이스의 개수 T가 주어지고, 그 아래로 각 테스트 케이스가 주어진다. 각 테스트 케이스의 첫 번째 줄에 N 이 주어진다.

출력

출력의 각 줄은 '#t'로 시작하고, 공백을 한 칸 둔 다음 정답을 출력한다. (t는 테스트 케이스의 번호를 의미하며 1부터 시작한다.)

예시

입력	출력
10   6791400 1646400 1425600 8575 185625 6480 1185408 6561 25 330750	#1 3 2 2 3 1 #2 6 1 2 3 0 #3 6 4 2 0 1 #4 0 0 2 3 0 #5 0 3 4 0 1 #6 4 4 1 0 0 #7 7 3 0 3 0 #8 0 8 0 0 0 #9 0 0 2 0 0 #10 1 3 3 2 0

---

2. 문제풀이

2, 3, 5, 6, 11 로 나누어 계산하는데 큰값부터 나누어 계산해봅니다. 입력값인 N을 11로 나누었을때 소수가 나온다면 6으로 바로넘어갑니다. 만약 나누어진다면 11로 나눈 값을 N에 저장하고 11로 나눈값을 카운팅합니다. 이렇게 2까지 가게되거나 N이 0이된다면 지금까지 카운팅한 값들을 출력합니다.

 

---

3. 소스코드

#include <iostream>
#include <vector>
 
using namespace std;
//1945 D2 간단한 소인수 분해
int main() {
    //전체 반복횟수 입력받고 반복, 입력숫자, 나눌값
    int len, num, a[5] = { 11, 7, 5, 3, 2 };
    cin >> len;
    for (int l = 1; l <= len; l++) {
        //a~e까지 체크용
        vector<int> arr(5, 0);
        cin >> num;
        for (int i = 0; i < 5; i++) {
            //값이 0이 될때까지 반복
            while (num) {
                //나눌때 소숫자리가 발생하지 않는다면
                if ((num / a[i]) == (num / float(a[i]))) {
                    //카운트 증가 후 나눈값 저장
                    arr[i]++;
                    num /= a[i];
                }
                //소숫자리가 나올경우 작은수로 넘어간다.
                else    break;
            }
        }
        cout << "#" << l;
        for (int i = 4; i >= 0; i--) {
            cout << " " << arr[i];
        }
        cout << endl;
    }
    return 0;
}