一、 课前预习：小白必懂的3个核心概念
在动手写代码前，我们需要先搞懂三个核心概念，这决定了你能不能看懂后续的代码逻辑。
1. 进程 vs 线程（工厂与工人的比喻）
- 进程（Process）：就像一个工厂。工厂有自己独立的厂房、水电资源（独立的内存空间）。
- 线程（Thread）：就像工厂里的工人。一个工厂里可以有多个工人同时干活。工人们共享工厂的资源（共享全局变量、堆内存），但每个工人有自己独立的工作台（独立的栈空间）。
- 多线程：就是雇佣多个工人，把一个大任务拆成几份，大家同时干，从而缩短总耗时。
2. 什么是试除法？（6k±1 优化）
- 效率不高：判断数字 n 是不是质数，从 2 一直除到 n-1。
- 效率提高：其实只需要除到根号n 即可。如果 n 有一个大于根号n的因子，那它必定有一个小于根号n的因子。
- 优化（6k±1）：数学规律表明，大于3的质数，一定分布在 6的倍数 的两侧（即 6k-1 或 6k+1）。利用这个规律，我们可以直接跳过大量不必要的判断，将效率提升约 3 倍！
3. 什么是 pthread？
Linux 下写多线程，使用的是 POSIX 线程库（简称 pthread）。它提供了一堆 C 语言 API，让你能创建工人（pthread_create）、分配任务、等工人干完活（pthread_join）。
二、 作业1：单线程版本（1个工人干所有的活）
这个版本是基础，我们只用一个主线程（也就是程序本身）来遍历 2 到 1 亿，挨个判断。
#include <stdio.h> // 标准输入输出（printf）
#include <stdlib.h> // 标准库
#include <sys/time.h> // 用于获取高精度的时间（gettimeofday）
// 定义我们要统计的最大范围：1亿
// 注意：数字后面加 L 表示 Long（长整型），防止数字太大超出 int 范围导致溢出
#define MAX_N 100000000L
/**
* 【核心函数】：试除法判断一个数 n 是否为质数（6k±1 优化版）
* 返回值：1 表示是质数，0 表示不是质数
*/
int is_prime(long n) {
if (n <= 1) return 0; // 1. 小于等于1的数不是质数
if (n <= 3) return 1; // 2. 2和3是质数，直接返回
if (n % 2 == 0 || n % 3 == 0) // 3. 排除掉2和3的倍数（干掉一半以上的数字）
return 0;
// 4. 【6k±1 优化法】：只检查 6k-1 (i) 和 6k+1 (i+2)
for (long i = 5; i * i <= n; i += 6) {
if (n % i == 0 || n % (i + 2) == 0)
return 0;
}
return 1; // 5. 没找到因子，是质数
}
/**
* 【辅助函数】：获取当前的精确时间（秒 + 微秒）
* 为什么不用 time()？因为 time() 只能精确到秒，程序跑得快的时候测不准。
*/
double get_time() {
struct timeval tv;
gettimeofday(&tv, NULL);
return tv.tv_sec + tv.tv_usec / 1000000.0;
}
int main() {
double start = get_time(); // 记录开始时间
long count = 0;
// 从 2 遍历到 1亿，挨个判断
for (long i = 2; i <= MAX_N; i++) {
if (is_prime(i)) {
count++;
}
}
double end = get_time(); // 记录结束时间
printf("============================================\\n");
printf(" 【单线程】质数统计（试除法）\\n");
printf("============================================\\n");
printf(" 统计范围: [2, %ld]\\n", MAX_N);
printf(" 质数个数: %ld\\n", count);
printf(" 总耗时: %.3f 秒\\n", end – start);
printf("============================================\\n");
return 0;
}
三、 作业2：多线程版本
这个版本是重头戏。我们要把 1亿 个数字“切块”，分给多个线程同时去算。
1. 架构设计图
┌──────────────┐
│ 主线程 │
│ 创建N个工作线程│
└──────┬───────┘
┌───────────┬───┴────┬───────────┐
┌─────▼─────┐ ┌───▼────┐ ┌▼────────┐ ┌▼────────┐
│ 线程 0 │ │线程 1 │ │线程 2 │ │线程 N-1 │
│[2, 2500万]│ │[2500万,│ │[5000万, │ │[7500万, │
│ 试除判断 │ │ 5000万]│ │ 7500万] │ │ 1亿] │
│ 独立计数 │ │ 试除判断│ │ 试除判断│ │ 试除判断│
└─────┬─────┘ └───┬────┘ └────┬────┘ └────┬────┘
└───────────┴─────┬─────┴───────────┘
┌─────▼─────┐
│ 主线程 │
│ 汇总结果 │ (无锁化，避免数据竞争)
└───────────┘
2. 完整代码
#include <stdio.h>
#include <stdlib.h>
#include <pthread.h> // 【重点】Linux 多线程编程必须引入的头文件
#include <sys/time.h>
#define MAX_N 100000000L
// ============== ⚠️ 避坑关键：函数前置声明 ==============
// 在 C 语言中，如果函数定义在 main 之后，必须在这里先声明，否则链接时会报错！
int is_prime(long n);
double get_time();
// ====================================================
int is_prime(long n) {
if (n <= 1) return 0;
if (n <= 3) return 1;
if (n % 2 == 0 || n % 3 == 0)
return 0;
for (long i = 5; i * i <= n; i += 6) {
if (n % i == 0 || n % (i + 2) == 0)
return 0;
}
return 1;
}
double get_time() {
struct timeval tv;
gettimeofday(&tv, NULL);
return tv.tv_sec + tv.tv_usec / 1000000.0;
}
/**
* 【重点结构体】：线程参数包
* pthread_create 只能传递【一个】 void* 指针参数。
* 传多个数据（起点、终点）必须打包成结构体！
*/
typedef struct {
long start; // 本线程负责判断的起始数字
long end; // 本线程负责判断的结束数字
long local_count; // 本线程统计的质数个数（用于将结果带回给主线程）
} ThreadArgs;
// is_prime 和 get_time 的实现与单线程完全一致，此处省略以节省篇幅…
int is_prime(long n) {
if (n <= 1) return 0;
if (n <= 3) return 1;
if (n % 2 == 0 || n % 3 == 0) return 0;
for (long i = 5; i * i <= n; i += 6) {
if (n % i == 0 || n % (i + 2) == 0) return 0;
}
return 1;
}
double get_time() {
struct timeval tv;
gettimeofday(&tv, NULL);
return tv.tv_sec + tv.tv_usec / 1000000.0;
}
/**
* 【线程工作函数】：每个线程（工人）实际执行的代码
*/
void *count_primes(void *arg) {
ThreadArgs *args = (ThreadArgs *)arg; // 1. 强转回结构体指针
long count = 0;
// 2. 只遍历分配给自己的区间 [start, end]
for (long i = args->start; i <= args->end; i++) {
if (is_prime(i)) {
count++;
}
}
// 3. 把算好的结果，存回结构体中（主线程就能看到了）
args->local_count = count;
return NULL; // 4. 线程结束
}
int main(int argc, char *argv[]) {
if (argc != 2) {
fprintf(stderr, "用法: %s <线程数>\\n", argv[0]);
return 1;
}
int num_threads = atoi(argv[1]);
if (num_threads <= 0 || num_threads > 64) {
fprintf(stderr, "线程数范围: 1 ~ 64\\n");
return 1;
}
double start_time = get_time();
// ===== 第1步：给每个线程分配任务（切蛋糕） =====
pthread_t *threads = malloc(num_threads * sizeof(pthread_t));
ThreadArgs *args = malloc(num_threads * sizeof(ThreadArgs));
for (int i = 0; i < num_threads; i++) {
// 【核心算法】：将 [2, MAX_N] 均匀切成 num_threads 份
args[i].start = 2 + (MAX_N – 1) * i / num_threads;
args[i].end = 2 + (MAX_N – 1) * (i + 1) / num_threads – 1;
if (i == num_threads – 1) args[i].end = MAX_N; // 防止漏掉最后一个数
args[i].local_count = 0;
}
// ===== 第2步：正式创建线程（招募工人开工） =====
for (int i = 0; i < num_threads; i++) {
int ret = pthread_create(&threads[i], NULL, count_primes, &args[i]);
if (ret != 0) {
fprintf(stderr, "线程创建失败!\\n");
return 1;
}
}
// ===== 第3步：主线程等待所有子线程干完活 =====
for (int i = 0; i < num_threads; i++) {
// pthread_join 让主线程“阻塞”，直到第 i 个线程执行完毕
pthread_join(threads[i], NULL);
}
// ===== 第4步：汇总所有线程的结果 =====
long total_count = 0;
for (int i = 0; i < num_threads; i++) {
total_count += args[i].local_count;
}
double end_time = get_time();
printf("================================================\\n");
printf(" 【多线程】质数统计（试除法）\\n");
printf("================================================\\n");
printf(" 线程数: %d\\n", num_threads);
printf(" 统计范围: [2, %ld]\\n", MAX_N);
printf(" 质数个数: %ld\\n", total_count);
printf(" 总耗时: %.3f 秒\\n", end_time – start_time);
printf("================================================\\n");
printf("\\n —- 各线程工作详情 —-\\n");
for (int i = 0; i < num_threads; i++) {
printf(" 线程 %d: 负责 [%ld, %ld] -> 找到 %ld 个质数\\n",
i, args[i].start, args[i].end, args[i].local_count);
}
free(threads);
free(args);
return 0;
}
💡 核心亮点解析
四、 编译运行与真实踩坑指南
1. 正确的编译命令
# 编译单多线程
gcc 你的文件的名字 记住要加后缀 例如 a.c -o 生成的程序名字
2. 🚨 真实踩坑记录：undefined reference 错误
很多新手在编译多线程代码时，会遇到如下满屏飘红的报错：
/usr/bin/ld: /tmp/ccEN5kAO.o: in function `count_primes':
d1.c:(.text+0x35): undefined reference to `is_prime'
/usr/bin/ld: d1.c:(.text+0xf4d): undefined reference to `get_time'
collect2: error: ld returned 1 exit status
🔍 为什么会报错？ 这是链接阶段的错误。在 C 语言中，如果函数的定义放在了 main 函数的后面，且在文件开头没有进行函数声明，编译器在自上而下扫描时就不认识这个函数，导致最终链接器找不到对应的符号。
✅ 解决方案： 永远养成好习惯，在 #include 头文件之后，立刻写上函数声明：
#include <stdio.h>
// … 其他头文件
// 👇 加上这两行，彻底告别 undefined reference！
int is_prime(long n);
double get_time();
int main() { … }
五、程序运行数据结果
1. 单线程与四线程
这是8核单线程下的总消耗时间
这是8核四线程下的总消耗时间
这是8核八线程下的总消耗时间
2. 为什么 8 线程没有达到 8 倍加速？
当开启的线程数（8）超过了 CPU 的物理核心数（4） 时，操作系统需要频繁地在多个线程之间进行上下文切换（Context Switch）。保存和恢复寄存器状态需要消耗额外的 CPU 时间，这就是所谓的“边际效益递减”。这证明了：线程数并非越多越好，匹配物理核心数才是最优解。
