#include <cstdio>
#include <mpi.h>
#include <cmath>

// 计算每个进程的实际计算成本（考虑素数检测的复杂度）
long long estimate_cost(int start, int end, int step) {
    long long total_cost = 0;
    for (int i = start; i <= end; i += step) {
        // 素数检测的成本约为 O(i)，即需要检查 i-2 次
        total_cost += (i - 2);
    }
    return total_cost;
}

int main(int argc, char *argv[]) {
    int id, p;
    MPI_Init(&argc, &argv);
    MPI_Comm_size(MPI_COMM_WORLD, &p);
    MPI_Comm_rank(MPI_COMM_WORLD, &id);

    int n = 100000;
    if (argc == 2) {
        n = atoi(argv[1]);
    }

    // 计算每个进程的计算成本
    int start = 2 + id;
    int end = n;
    long long my_cost = estimate_cost(start, end, p);

    // 收集所有进程的成本
    long long *costs = nullptr;
    if (id == 0) {
        costs = new long long[p];
    }
    MPI_Gather(&my_cost, 1, MPI_LONG_LONG_INT, costs, 1, MPI_LONG_LONG_INT, 0, MPI_COMM_WORLD);

    if (id == 0) {
        printf("\n=== 计算成本分析 (N=%d, P=%d) ===\n", n, p);
        printf("进程号\t数字数量\t估计计算成本\t成本占比\n");
        printf("------------------------------------------------------------\n");
        
        long long total_cost = 0;
        for (int i = 0; i < p; i++) {
            total_cost += costs[i];
        }
        
        for (int i = 0; i < p; i++) {
            int count = (n - (2 + i)) / p + 1;
            double percentage = 100.0 * costs[i] / total_cost;
            printf("%d\t%d\t\t%lld\t\t%.2f%%\n", i, count, costs[i], percentage);
        }
        
        printf("------------------------------------------------------------\n");
        printf("总计算成本: %lld\n", total_cost);
        printf("平均成本: %lld\n", total_cost / p);
        printf("最大成本: %lld (进程0)\n", costs[0]);
        printf("最小成本: %lld (进程%d)\n", costs[p-1], p-1);
        printf("\n");
        
        double imbalance = 100.0 * (costs[0] - costs[p-1]) / (double)costs[0];
        printf("=== 负载不均衡分析 ===\n");
        printf("成本不均衡度: %.2f%%\n", imbalance);
        printf("\n");
        printf("说明：\n");
        printf("- 进程0检测的数字最小（2, %d, %d, ...），但每个数字的检测成本高\n", 2+p, 2+2*p);
        printf("- 进程%d检测的数字最大（%d, %d, ...），但每个数字的检测成本更高！\n", p-1, 2+(p-1), 2+2*(p-1));
        printf("\n");
        printf("关键问题：\n");
        printf("虽然各进程检查的数字数量相近，但大数字的素数检测需要更多除法运算。\n");
        printf("例如：检测2需要0次除法，检测100000需要99998次除法！\n");
        printf("这导致进程间存在严重的负载不均衡。\n");
        printf("\n");

        delete[] costs;
    }

    MPI_Finalize();
    return 0;
}