#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;
}