Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /* Dasprog C - 2019
- William Handi Wijaya
- 0087
- Program untuk mencari LCM (KPK) dengan menggunakan
- pembagian bilangan prima.
- */
- #include <stdio.h>
- #include <math.h>
- #include <string.h>
- void setPrime(int fact, int prime[]);
- int main()
- {
- // Declare needed variable
- int fact, prime[168], tes, amount, count, loop = 0;
- unsigned long long kpk;
- setPrime(fact, prime);
- // Get test case
- scanf("%d", &tes);
- // for every testcase
- for (int t = 0; t < tes; t++)
- {
- kpk = 1;
- loop = 0;
- scanf("%d", &amount);
- int num[amount];
- int pangkat[amount][168];
- memset(pangkat, 0, 168*amount*sizeof(int));
- // Input num
- for (int i = 0; i < amount; i++)
- {
- scanf("%d", &num[i]);
- }
- // Semua angka dibagi prime[j]
- // count = 0;
- for (int j = 0; j < 168; j++)
- {
- // tiap angka
- count = 0;
- for (int i = 0; i < amount; i++)
- {
- if (num[i] != 1 && num[i] != 0)
- {
- while (num[i] % prime[j] == 0)
- {
- num[i] /= prime[j];
- pangkat[i][j]++;
- }
- }
- else count++;
- }
- loop++;
- if (count == amount) break;
- }
- // Ambil pangkat j terbesar
- int terbesar[loop];
- for (int j = 0; j < loop; j++)
- {
- terbesar[j] = pangkat[0][j];
- for (int i = 1; i < amount; i++)
- {
- if (pangkat[i][j] > terbesar[j])
- {
- terbesar[j] = pangkat[i][j];
- }
- }
- }
- // Cari KPK
- for (int i = 0; i < loop; i++)
- {
- kpk *= (unsigned long long) pow(prime[i], terbesar[i]);
- }
- // Print KPK
- printf("%llu\n", kpk);
- }
- }
- void setPrime(int fact, int prime[])
- {
- int p = 0;
- for(int i = 1; i <= 1000; i++)
- {
- fact = 0;
- for(int j = 1; j <= 1000; j++)
- {
- if(i % j ==0)
- {
- fact++;
- }
- }
- if(fact == 2)
- {
- prime[p] = i;
- p++;
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement