C++/BOJ

#8 - 20946번 합성인수분해 (시간초과)

yunhyegyeong 2021. 8. 16. 12:44
728x90

문제

소인수분해란 어떤 자연수를 소수의 곱으로 나타내는 것이다. 정수론을 끔찍하게 싫어하는 연두는 소수만 보면 치가 떨려, 대신에 자연수를 합성수의 곱으로 나타내는 “합성인수분해”라는 것을 만들었다.

자연수 N의 합성인수분해는 다음의 조건을 모두 만족하는 수열 A로 정의한다.

  • A의 모든 원소는 합성수이다. (합성수란 1과 자기 자신 이외의 다른 약수를 가지는 정수이다.)
  • A의 모든 원소의 곱은 N이다.

하지만 연두는 N의 합성인수분해가 여러 개이거나 존재하지 않을 수도 있다는 것을 깨달았다. 연두를 대신해 N을 합성인수분해 해주는 프로그램을 만들어보자. 만약 가능한 결과가 여러 개일 경우, 사전 순으로 가장 앞서는 것을 선택해야 한다.

입력

다음과 같이 입력이 주어진다.

N 

출력

N의 합성인수분해 중 사전순으로 가장 앞서는 수열의 원소들을 순서대로 공백으로 구분하여 출력한다.

합성인수분해가 불가능하다면 대신에 -1을 출력한다.

제한

  • 2≤N≤1012
  • N은 정수다.

나의 풀이

2부터 n까지의 자연수로 나눈다. 나눈 수가 합성수이며 결과가 나누어 떨어지고 그 몫 또한 합성수일 경우를 구한다.

 

 

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include <iostream>
#include <cmath>
#include <set>
using namespace std;
 
multiset<int> print;
 
bool isnotPrime(int num) {
    if (num < 4)
        return false;
 
    int a = (int)sqrt(num);
 
    for (int i = 2; i <= a; i++)
        if (num % i == 0)
            return true;
        
    return false;
}
 
int com(int n) {
    for (int i = 2;i < n;i++) {
        if (n % i == 0 && isnotPrime(i) && isnotPrime(n / i)) {
            print.insert(i);
            return n / i;
        }
    }
    return 0;
}
 
 
int main() {
    int n;
    cin >> n;
 
    int count = 0;
    int a = com(n);
    int temp = a;
 
    while (true) {
        if (a == 0 && count == 0) {
            cout << -1;
            return 0;
        }
        else if (a == 0 && count != 0) {
            print.insert(temp);
            break;
        }
        else {
            temp = a;
            a = com(a);
            count++;
        }
    }
    
    for (auto i : print)
        cout << i << ' ';
 
    return 0;
}
 cs