(C++) ★Number Theory Upper-Beginner I - 3 Solved★

★ 9506 약수들의 합 ★

//9506
#include <iostream>
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int n,total;

	while(1){
        cin >> n;
        if(n==-1){
            break;
        }
        total = 1;
        vector<int> numbers = {};

        for(int x=2;x<n;x++){
            if(n%x==0){
                total+=x;
                numbers.push_back(x);
            }
        }

        if(total==n){
            sort(numbers.begin(), numbers.end());
            cout << n << " = 1";
            for(int num : numbers){
                cout << " + " << num;
            }
            cout << endl;
        }
        else cout << n << " is NOT perfect." << endl;

    }
	return 0;
}

 

🧚‍♂️ 가변 배열 vector<int> numbers = {} 만들어 놓고, 약수일 때 numbers.push_back(x); 사용.

 

🧚‍♂️ 한 개 입력 당 바로 한 개 결과 출력해야 하므로 cout << endl; 적절히 배치 필요

---

★ 11653 소인수분해 ★

//11653
#include <iostream>
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;

bool is_prime(int n){
    for(int x=2;x<=sqrt(n);x++){
        if(n%x==0){
            return false;
        }
    }
    return true;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int N;
    cin >> N;

    vector<int> divisors = {};
    vector<int> prime_factors = {};
    vector<int> answers = {};

    if(N==1){
        return 0;
    }

    for(int n=2;n<=N;n++){
        if(N%n==0){
            divisors.push_back(n);
        }
    }

    for(int divisor : divisors){
        if(is_prime(divisor)){
            prime_factors.push_back(divisor);
        }
    }

    for(int prime_factor : prime_factors){
        while(N%prime_factor==0){
            N/=prime_factor;
            answers.push_back(prime_factor);
        }
        if(N==1) break;
    }

    sort(answers.begin(),answers.end());
    for(int answer:answers){
        cout << answer << '\n';
    }
    
	return 0;
}

 

🧚‍♂️ 소인수분해의 정의에 따라 약수 배열 / 소인수 종류 배열 / 그리고 정답이 들어간 소인수 배열까지 차례대로 구하면서 진행.

 

🧚‍♂️sort(), push_back() 적절히 사용

 

🧚‍♂️ 소수 판정은 #include <cmath> 사용해서 sqrt(n)(포함)까지 진행

---

★ 1934 최소공배수 ★

//1934
#include <iostream>
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <cmath>
#include <map>
#include <set>
using namespace std;

int get_GCD(int a, int b){
    while(b!=0){
        int tmp;
        tmp = a;
        a = b;
        b = tmp % b;
    }
    return a;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int T, A, B, gcd;
    cin >> T;

    while(T--){
        cin >> A >> B;
        if(A>=B){
            gcd = get_GCD(A,B);
        }
        else{
            gcd = get_GCD(B,A);
        }
        cout << (A * B) / gcd << endl;
    }
	return 0;
}

 

🧚‍♂️ 유클리드 호제법(큰 수는 작은 수로, 작은 수는 큰 수를 작은 수로 나눈 나머지 / 그리고 작은 수가 0이 될 때까지 돌리기)으로 두 수의 최대공약수를 구하고, A x B = G x L 공식을 활용해 최소공배수 L을 출력하면 된다.

---