Advertisement
Infernale

GGCD

Jan 17th, 2019
486
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C 0.86 KB | None | 0 0
  1. #include <stdio.h>
  2.  
  3. int gcd(int a, int b){
  4.     return a==0?b:gcd(b%a,a);
  5. }
  6.  
  7. void insertionSort(int arr[], int n){
  8.    int key, j;
  9.    for(int i=1;i<n;i++){
  10.        key = arr[i];
  11.        j = i-1;
  12.        while (j>=0 && arr[j]>key){
  13.            arr[j+1] = arr[j];
  14.            j--;
  15.        }
  16.        arr[j+1] = key;
  17.    }
  18. }
  19.  
  20. int findGCD(int arr[], int n){
  21.     int high=0;
  22.     for(int i=n-1;i>=0;i--){
  23.         for(int j=i-1;j>=0;j--){
  24.             int temp = gcd(arr[i], arr[j]);
  25.             if(arr[j]<high){
  26.                 break;
  27.             }else if(temp>high){
  28.                 high = temp;
  29.             }
  30.         }
  31.     }
  32.     return high;
  33. }
  34.  
  35. int main(){
  36.     int tc;
  37.     scanf("%d", &tc);
  38.     for(int i=1;i<=tc;i++){
  39.         int n, product=1, high=0, check;
  40.         scanf("%d", &n);
  41.         int data[n];
  42.         for(int j=0;j<n;j++){
  43.             scanf("%d", &data[j]);
  44.         }
  45.         insertionSort(data, n);
  46.         printf("Case #%d: %d\n", i, findGCD(data, n));
  47.     }
  48.     return 0;
  49. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement