Advertisement
Guest User

Untitled

a guest
Nov 20th, 2019
115
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C 1.86 KB | None | 0 0
  1. /* Dasprog C - 2019
  2. William Handi Wijaya
  3. 0087
  4.  
  5. Program untuk mencari LCM (KPK) dengan menggunakan
  6. pembagian bilangan prima.
  7. */
  8.  
  9. #include <stdio.h>
  10. #include <math.h>
  11. #include <string.h>
  12.  
  13. void setPrime(int fact, int prime[]);
  14.  
  15. int main()
  16. {
  17.     // Declare needed variable
  18.     int fact, prime[168], tes, amount, count, loop = 0;
  19.     unsigned long long kpk;
  20.  
  21.     setPrime(fact, prime);
  22.  
  23.     // Get test case
  24.     scanf("%d", &tes);
  25.  
  26.     // for every testcase
  27.     for (int t = 0; t < tes; t++)
  28.     {
  29.         kpk = 1;
  30.         loop = 0;
  31.         scanf("%d", &amount);
  32.         int num[amount];
  33.         int pangkat[amount][168];
  34.         memset(pangkat, 0, 168*amount*sizeof(int));
  35.  
  36.         // Input num
  37.         for (int i = 0; i < amount; i++)
  38.         {
  39.             scanf("%d", &num[i]);
  40.         }
  41.  
  42.         // Semua angka dibagi prime[j]
  43.         // count = 0;
  44.         for (int j = 0; j < 168; j++)
  45.         {
  46.             // tiap angka
  47.             count = 0;
  48.             for (int i = 0; i < amount; i++)
  49.             {
  50.                 if (num[i] != 1 && num[i] != 0)
  51.                 {
  52.                     while (num[i] % prime[j] == 0)
  53.                     {
  54.                         num[i] /= prime[j];
  55.                         pangkat[i][j]++;
  56.                     }
  57.                 }
  58.                 else count++;
  59.             }
  60.             loop++;
  61.             if (count == amount) break;
  62.         }
  63.  
  64.         // Ambil pangkat j terbesar
  65.         int terbesar[loop];
  66.         for (int j = 0; j < loop; j++)
  67.         {
  68.             terbesar[j] = pangkat[0][j];
  69.             for (int i = 1; i < amount; i++)
  70.             {
  71.                 if (pangkat[i][j] > terbesar[j])
  72.                 {
  73.                     terbesar[j] = pangkat[i][j];
  74.                 }
  75.             }
  76.         }
  77.  
  78.         // Cari KPK
  79.         for (int i = 0; i < loop; i++)
  80.         {
  81.             kpk *= (unsigned long long) pow(prime[i], terbesar[i]);
  82.         }
  83.  
  84.         // Print KPK
  85.         printf("%llu\n", kpk);
  86.     }
  87. }
  88.  
  89. void setPrime(int fact, int prime[])
  90. {
  91.     int p = 0;
  92.     for(int i = 1; i <= 1000; i++)
  93.     {
  94.         fact = 0;
  95.         for(int j = 1; j <= 1000; j++)
  96.         {
  97.             if(i % j ==0)
  98.             {
  99.                 fact++;
  100.             }
  101.         }
  102.         if(fact == 2)
  103.         {
  104.             prime[p] = i;
  105.             p++;
  106.         }
  107.     }
  108. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement