使用pthreads加速0到N质数计数：线程用法及性能提升验证

嘿，Connor！咱们来一步步解决你的问题：

首先明确回答你的核心疑问：pthreads确实是可以并行执行的——只要你的CPU有多个物理核心，这些线程就能同时跑在不同核心上，理论上能大幅提升计算速度。不过你的代码里有几个关键问题，导致它可能没法发挥出多线程的优势，甚至可能比单线程还慢，咱们来逐一梳理：

你的代码里做得对的地方 #

• 你用了pthread_mutex_t来保护共享变量counter，这是正确的——多个线程同时修改同一个全局变量时，互斥锁能避免竞态条件（比如两个线程同时读取counter，各自加1后写回去，导致最终少加了1）。

需要修正的问题与优化点 #

1. is_prime函数效率极低 #

这是最影响性能的点，不管单线程还是多线程都得先改：
你现在的循环是for (int i=3; i < n; i += 2)，但实际上判断一个数n是否为质数，只需要循环到sqrt(n)就够了——如果n有大于sqrt(n)的因数，那它必然有一个对应的小于sqrt(n)的因数。这个修改能把is_prime的时间复杂度从O(n)降到O(√n)，性能提升非常明显。

2. 锁的粒度太大，严重拖慢并行度 #

你现在每次发现质数就加锁，还在锁里调用printf——printf本身也是线程安全的（内部会加锁），这导致你的线程大部分时间都在等待锁释放，根本没法真正并行工作。

优化方案：每个线程先统计自己负责范围内的质数数量（用局部变量），等自己的任务全部完成后，再把局部值加到全局counter里，这样只需要加一次锁，锁竞争几乎为零。

3. main函数没有等待所有线程完成 #

你在main里创建完线程后直接调用pthread_exit(NULL)，这会导致main线程提前退出，而其他工作线程可能还没执行完，最终的counter结果会不准确。正确的做法是用pthread_join等待每一个线程执行完毕。

4. 任务分配有漏洞 #

当NUM_COUNT不能被NUM_THREADS整除时，最后一个线程会少处理一些数。比如如果NUM_COUNT是801，那前7个线程各处理100个数（0-99,100-199...600-699），第8个线程处理700-799，漏掉了800-801。我们需要调整任务分配逻辑，让最后一个线程处理到NUM_COUNT的末尾。

优化后的完整代码 #

#include <pthread.h>
#include <stdio.h>
#include <math.h>
#define NUM_COUNT 800
#define NUM_THREADS 8

int counter = 0; // 全局质数计数器
pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER;

// 优化后的质数判断函数
int is_prime(int n) {
    if (n < 2) return 0;
    if (n == 2) return 1;
    if (n % 2 == 0) return 0;
    int sqrt_n = sqrt(n); // 只计算一次sqrt，避免循环里重复计算
    for (int i = 3; i <= sqrt_n; i += 2) {
        if (n % i == 0) return 0;
    }
    return 1;
}

// 线程函数：统计自己范围内的质数，最后合并到全局计数器
void *count_primes(void *threadid) {
    int thread_id = (int)threadid;
    int range_size = NUM_COUNT / NUM_THREADS;
    // 计算当前线程的起始和结束范围
    int thread_start = thread_id * range_size;
    int thread_end = (thread_id == NUM_THREADS - 1) ? NUM_COUNT : thread_start + range_size;
    
    int local_count = 0; // 局部计数器，避免锁竞争
    for (int n = thread_start; n < thread_end; n++) {
        if (is_prime(n)) {
            local_count++;
            // 如果需要打印发现的质数，也可以在这里打印，不需要锁（因为是线程自己的输出）
            // printf("Prime found: %d\n", n);
        }
    }
    
    // 最后合并局部结果到全局计数器，只加一次锁
    pthread_mutex_lock(&mutex);
    counter += local_count;
    printf("Thread %d finished, added %d primes. Total now: %d\n", thread_id, local_count, counter);
    pthread_mutex_unlock(&mutex);
    
    pthread_exit(NULL);
}

int main(int argc, char *argv[]) {
    pthread_t threads[NUM_THREADS];
    
    // 创建所有线程
    for (int i = 0; i < NUM_THREADS; i++) {
        pthread_create(&threads[i], NULL, count_primes, (void *)i);
    }
    
    // 等待所有线程执行完毕
    for (int i = 0; i < NUM_THREADS; i++) {
        pthread_join(threads[i], NULL);
    }
    
    printf("Final total primes from 0 to %d: %d\n", NUM_COUNT - 1, counter);
    
    pthread_mutex_destroy(&mutex); // 销毁互斥锁，释放资源
    return 0;
}

优化后的效果 #

经过这些修改后，你的多线程程序会真正发挥并行优势：

• 每个线程在自己的范围内独立计算，几乎不需要等待锁
• is_prime的效率提升了几个数量级，尤其是处理大数时
• 所有线程完成后才会输出最终结果，保证准确性

在多核CPU上，这个程序的速度会接近单线程版本的8倍（当然实际因为CPU缓存、线程调度等因素，可能略低于这个数，但提升会非常明显）。

内容的提问来源于stack exchange，提问作者Connor D