Repository navigation
Expand file tree
/
Copy pathFPB-GCD-KPK-LCM.cpp
More file actions
175 lines (141 loc) · 5.03 KB
/
Copy pathFPB-GCD-KPK-LCM.cpp
File metadata and controls
175 lines (141 loc) · 5.03 KB
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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
#include <iostream>
#include <cmath>
#include <vector>
#include <map>
using namespace std;
long long fpb_gcd_naive_of_two_numbers(long long a, long long b){
long long min_val = min(a,b);
for (long long i = min_val; i > 0; i--){
if (a % i == 0 && b % i == 0){
return i;
}
}
return 1;
}
/*
vector<long long> prime_factorization(long long n){
vector<long long> factors;
// Membagi dengan 2
while (n % 2 == 0){
factors.push_back(2);
n /= 2;
}
// Membagi dengan angka ganjil dimulai dari 3
for (long long i = 3; i <= sqrt(n); i+=2){
while (n % i){
factors.push_back(i);
n /= i;
}
}
// Jika n lebih besar dari 2, maka itu adalah faktor prima
if (n > 2){
factors.push_back(n);
}
return factors;
}
*/
// Faktorisasi Prima (menggunakan map untuk menyimpan faktor dan pangkatnya)
map<long long, int> prime_factorization(long long n){
map<long long, int> factorPrimes;
// Membagi dengan 2
while (n % 2 == 0){
factorPrimes[2]++;
n /= 2;
}
// Membagi dengan angka ganjil dimulai dari 3
for (long long i = 3; i <= sqrt(n); i+=2){
while (n % i == 0){
factorPrimes[i]++;
n /= i;
}
}
// Jika n lebih besar dari 2, maka itu adalah faktor prima
if (n > 2){
factorPrimes[n]++;
}
return factorPrimes;
}
// Mencari FPB dengan Faktorisasi Prima
long long fpb_gcd_prime_factored_of_two_numbers(long long a, long long b){
// Mendapatkan faktor prima dari a dan b dalam bentuk map (prime, exponent)
map<long long, int> prime_factors_a = prime_factorization(a);
map<long long, int> prime_factors_b = prime_factorization(b);
long long fpb = 1;
// Menyusun faktor-faktor yang sama dan mengambil pangkat yang terkecil
for (auto &factor_a : prime_factors_a){
long long prime = factor_a.first;
int exponent_a = factor_a.second;
if (prime_factors_b.find(prime) != prime_factors_b.end()){
// Jika faktor sama, ambil pangkat terkecil
int exponent_b = prime_factors_b[prime];
int common_exponent = min(exponent_a, exponent_b);
// Kalikan faktor dengan pangkat terkecil
fpb *= pow(prime, common_exponent);
}
}
return fpb;
}
long long fpb_gcd_euclid_iteration(long long a, long long b){
while (b != 0){
long long temp = b;
b = a % b;
a = temp;
}
return a;
}
long long fpb_gcd_euclid_recursive(long long a, long long b){
if (b == 0){
return a;
}
return fpb_gcd_euclid_recursive(b, a % b);
}
long long kpk_lcm_naive(long long a, long long b){
long long max_val = max(a,b);
while (true){
if (max_val % a == 0 && max_val % b == 0){
return max_val;
}
max_val++;
}
}
long long kpk_lcm_iteration(long long a, long long b){
return(a * b) / fpb_gcd_euclid_iteration(a, b);
}
long long kpk_lcm_recursive(long long a, long long b){
return(a * b)/ fpb_gcd_euclid_recursive(a, b);
}
int main(){
long long a, b;
// Masukkan dua angka untuk dicari nilai FPB atau Greatest Common Divisor nya
cout << "Masukkan angka pertama: ";
cin >> a;
cout << "Masukkan angka kedua: ";
cin >> b;
cout << "FPB atau GCD dengan metode sederhana dari " << a << " dan " << b << " adalah " << fpb_gcd_naive_of_two_numbers(a, b) << endl;
cout << "FPB atau GCD dengan metode faktorisasi prima dari " << a << " dan " << b << " adalah " << fpb_gcd_prime_factored_of_two_numbers(a, b) << endl;
cout << "FPB atau GCD dengan metode iterasi euclid dari " << a << " dan " << b << " adalah " << fpb_gcd_euclid_iteration(a, b) << endl;
cout << "FPB atau GCD dengan metode rekursif euclid dari " << a << " dan " << b << " adalah " << fpb_gcd_euclid_recursive(a, b) << endl;
cout << "KPK atau LCM dengan metode sederhana dari " << a << " dan " << b << " adalah " << kpk_lcm_naive(a, b) << endl;
cout << "KPK atau LCM dengan metode iterasi euclid dari " << a << " dan " << b << " adalah " << kpk_lcm_iteration(a, b) << endl;
cout << "KPK atau LCM dengan metode rekursif euclid dari " << a << " dan " << b << " adalah " << kpk_lcm_recursive(a, b) << endl;
}
/*
Buku Pemrograman Kompetitif Dasar
Panduan Memulai OSN Informatika, ACM-ICPC, dan Sederajat
Ikatan Alumni TOKI
Algoritma 7 Algoritma Euclid untuk mencari FPB secara rekursif.
1: function EUCLID(a,b)
2: if b = 0 then
3: return a
4: else
5: return EUCLID(b,a mod b)
6: end if
7: end function
contoh input dan output :
Masukkan angka pertama: 4725
Masukkan angka kedua: 7875
FPB atau GCD dengan metode sederhana dari 4725 dan 7875 adalah 1575
FPB atau GCD dengan metode faktorisasi prima dari 4725 dan 7875 adalah 1575
FPB atau GCD dengan metode iterasi euclid dari 4725 dan 7875 adalah 1575
FPB atau GCD dengan metode rekursif euclid dari 4725 dan 7875 adalah 1575
*/