fork download
copy 
  1. #include <mpi.h>
  2. #include <iostream>
  3. #include <vector>
  4. #include <cmath>
  5. #include <algorithm>
  6.  
  7. void sieve_of_eratosthenes(int start, int end, std::vector<int>& primes) {
  8.     std::vector<bool> is_prime(end - start + 1, true);
  9.     int limit = std::sqrt(end);
  10.  
  11.     for (int i = 2; i <= limit; ++i) {
  12.         int multiple_start = std::max(i * i, (start + i - 1) / i * i);
  13.         for (int j = multiple_start; j <= end; j += i) {
  14.             is_prime[j - start] = false;
  15.         }
  16.     }
  17.  
  18.     for (int i = start; i <= end; ++i) {
  19.         if (i > 1 && is_prime[i - start]) {
  20.             primes.push_back(i);
  21.         }
  22.     }
  23. }
  24.  
  25. int main(int argc, char* argv[]) {
  26.     MPI_Init(&argc, &argv);
  27.  
  28.     int rank, size;
  29.     MPI_Comm_rank(MPI_COMM_WORLD, &rank);
  30.     MPI_Comm_size(MPI_COMM_WORLD, &size);
  31.  
  32.     if (argc < 2) {
  33.         if (rank == 0) {
  34.             std::cerr << "Usage: " << argv[0] << " <n>" << std::endl;
  35.         }
  36.         MPI_Finalize();
  37.         return 1;
  38.     }
  39.  
  40.     int n = std::atoi(argv[1]);
  41.     double start_time = MPI_Wtime();
  42.  
  43.     // Distribute ranges among processes
  44.     int local_start = (rank * n) / size + 1;
  45.     int local_end = ((rank + 1) * n) / size;
  46.  
  47.     std::vector<int> primes;
  48.     sieve_of_eratosthenes(local_start, local_end, primes);
  49.  
  50.     // Compute local maximum gap
  51.     int local_max_gap = 0;
  52.     for (size_t i = 1; i < primes.size(); ++i) {
  53.         int gap = primes[i] - primes[i - 1];
  54.         local_max_gap = std::max(local_max_gap, gap);
  55.     }
  56.  
  57.     // Share boundary primes with neighboring processes
  58.     int left_prime = (primes.empty() ? 0 : primes.front());
  59.     int right_prime = (primes.empty() ? 0 : primes.back());
  60.     int left_neighbor_prime = 0, right_neighbor_prime = 0;
  61.  
  62.     MPI_Request requests[4];
  63.     MPI_Isend(&left_prime, 1, MPI_INT, rank - 1, 0, MPI_COMM_WORLD, &requests[0]);
  64.     MPI_Isend(&right_prime, 1, MPI_INT, rank + 1, 1, MPI_COMM_WORLD, &requests[1]);
  65.     MPI_Irecv(&left_neighbor_prime, 1, MPI_INT, rank - 1, 1, MPI_COMM_WORLD, &requests[2]);
  66.     MPI_Irecv(&right_neighbor_prime, 1, MPI_INT, rank + 1, 0, MPI_COMM_WORLD, &requests[3]);
  67.  
  68.     MPI_Waitall(4, requests, MPI_STATUSES_IGNORE);
  69.  
  70.     // Adjust gaps with boundary primes
  71.     if (left_neighbor_prime > 0 && !primes.empty()) {
  72.         int boundary_gap = primes.front() - left_neighbor_prime;
  73.         local_max_gap = std::max(local_max_gap, boundary_gap);
  74.     }
  75.     if (right_neighbor_prime > 0 && !primes.empty()) {
  76.         int boundary_gap = right_neighbor_prime - primes.back();
  77.         local_max_gap = std::max(local_max_gap, boundary_gap);
  78.     }
  79.  
  80.     // Find global maximum gap using reduction
  81.     int global_max_gap = 0;
  82.     MPI_Reduce(&local_max_gap, &global_max_gap, 1, MPI_INT, MPI_MAX, 0, MPI_COMM_WORLD);
  83.  
  84.     double end_time = MPI_Wtime();
  85.     if (rank == 0) {
  86.         std::cout << "Max Gap: " << global_max_gap << std::endl;
  87.         std::cout << "Time: " << end_time - start_time << " seconds" << std::endl;
  88.     }
  89.  
  90.     MPI_Finalize();
  91.     return 0;
  92. }
  93.  
Success #stdin #stdout #stderr 0.31s 40492KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
Error: unexpected symbol in "void sieve_of_eratosthenes"
Execution halted
https://ideone.com/eNVYqp
language:
R (R 3.5.2)
created:
21 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!