#include <iostream>  
#include <vector>  
#include <cmath>  
#include <mpi.h>  
  
// Function to check if a number is prime  
bool isPrime(int num) {  
   if (num <= 1) return false;  
   for (int i = 2; i <= sqrt(num); i++) {  
      if (num % i == 0) return false;  
   }  
   return true;  
}  
  
// Function to find the largest gap between consecutive prime numbers  
int findLargestGap(int start, int end) {  
   int largestGap = 0;  
   int prevPrime = -1;  
   for (int i = start; i <= end; i++) {  
      if (isPrime(i)) {  
        if (prevPrime != -1) {  
           largestGap = std::max(largestGap, i - prevPrime);  
        }  
        prevPrime = i;  
      }  
   }  
   return largestGap;  
}  
  
int main(int argc, char** argv) {  
   MPI_Init(&argc, &argv);  
  
   int rank, size;  
   MPI_Comm_rank(MPI_COMM_WORLD, &rank);  
   MPI_Comm_size(MPI_COMM_WORLD, &size);  
  
   int n;  
   if (rank == 0) {  
      std::cout << "Enter the value of n: ";  
      std::cin >> n;  
   }  
  
   MPI_Bcast(&n, 1, MPI_INT, 0, MPI_COMM_WORLD);  
  
   int chunkSize = n / size;  
   int start = rank * chunkSize + 2; // Start from 2, the first prime number  
   int end = (rank == size - 1) ? n : (start + chunkSize - 1);  
  
   double startTime = MPI_Wtime();  
   int largestGap = findLargestGap(start, end);  
   double endTime = MPI_Wtime();  
  
   int globalLargestGap;  
   MPI_Reduce(&largestGap, &globalLargestGap, 1, MPI_INT, MPI_MAX, 0, MPI_COMM_WORLD);  
  
   double timeTaken = endTime - startTime;  
   double totalTimeTaken;  
   MPI_Reduce(&timeTaken, &totalTimeTaken, 1, MPI_DOUBLE, MPI_MAX, 0, MPI_COMM_WORLD);  
  
   if (rank == 0) {  
      std::cout << "Largest gap between consecutive prime numbers less than " << n << ": " << globalLargestGap << std::endl;  
      std::cout << "Time taken: " << totalTimeTaken << " seconds" << std::endl;  
   }  
  
   MPI_Finalize();  
   return 0;  
}