#include <stdio.h>
#include <stdbool.h>

//method to calculate the sum
int sum(int* arr, int n) {
  // your code for sum
  int a = 0;
  for(int i = 0; i < n; i++)
  {
    a += arr[i];
  }
  return a;
}

int partitionFunc(int arr[], int left, int right){
  int pivot = arr[right];
  int partition = (left-1);
  for(int j = left; j <= right-1; j++)
  {
    if(arr[j] < pivot){
      partition++;
      int temp = arr[j];
      arr[j] = arr[partition];
      arr[partition] = temp;
    }
  }
  int t = arr[partition+1];
  arr[partition+1] = arr[right];
  arr[right] = t;

  return partition+1;
}

void quickSort(int* arr, int left, int right){
  if(left < right){
    int partition = partitionFunc(arr,left,right);
    quickSort(arr, left, partition-1);
    quickSort(arr, partition+1, right);
  }
}
int main(){

    int n;
    printf("Enter a positive integer: ");
    scanf("%d", &n);

    for(int i = 2; i < n; i++){
      bool is_prime = true;
      for(int j = 2; j <i; j++){
        if(i%j == 0){
          is_prime = false;
        }
      }
      if(is_prime){
        printf("%d \n", i);
      }
    }

  //task 3

    printf("\nTask 3 Arrays \n");
    int m;
    printf("Input Size of Array: ");
    scanf("%d", &m);
    int arr[m];

    for(int i = 0; i < m; i++){
      int t;
      printf("Input an integer: ");
      scanf("%d", &t);
      arr[i] = t;
    }

    int s = sum(arr, m);
    printf("Number of numbers: %d \n", m);
    for(int j = 0; j < m; j++){
       printf("Input %d: %i \n", (j+1), arr[j]);
    }
    printf("The sum is: %d", s);


    //task 4
    printf("\n");
    printf("\nQuick Sort\n");
    int x;
    printf("Input Size of Array: ");
    scanf("%d", &x);
    int arr2[x];

    for(int z = 0; z < x; z++){
      int y;
      printf("Input an integer: ");
      scanf("%d", &y);
      arr2[z] = y;
    }

    quickSort(arr2, 0, (x-1));
    printf("Sorted Array: \n");
    for(int j = 0; j < x; j++){
       printf("%d, ", arr2[j]);
    }
}