C 语言中计算素数的方法有三种：遍历法、埃拉托斯特尼筛法和费马小定理。遍历法逐个遍历整数，检查是否仅被 1 和自身整除。埃拉托斯特尼筛法用布尔数组标记素数，将非素数倍数标记为非素数。费马小定理基于数学定理，通过检验随机整数的指数运算结果来判断素数。
C语言中计算素数的方法
素数定义：
素数是指仅被 1 和自身整除的正整数（不包含 1）。
C语言中计算素数的方法：
方法 1：遍历法
OpenMP并行程序设计 WORD版
下载
本文档主要讲述的是OpenMP并行程序设计；OpenMP是一个编译器指令和库函数的集合，主要是为共享式存储计算机上的并行程序设计使用的。目前支持OpenMP的语言主要有Fortran，C/C++。 OpenMP在并行执行程序时，采用的是fork/join式并行模式，共享存储式并行程序就是使用fork/join式并行的。希望本文档会给有需要的朋友带来帮助；感兴趣的朋友可以过来看看
立即学习“C语言免费学习笔记（深入）”；
- 从 2 开始逐个遍历每个整数。
- 对于每个整数 n，检查它是否满足以下条件：
bool isPrime = true;
for (int i = 2; i <= n/2; i++) {
if (n % i == 0) {
isPrime = false;
break;
}
}
if (isPrime) {
// n 是素数
}方法 2：埃拉托斯特尼筛法
- 创建一个布尔数组，其中第 n 个元素表示数字 n 是否是素数。
- 从 2 开始，逐个遍历每个整数 n。
- 将数组中 n 的倍数标记为非素数。
- 在遍历结束后，数组中标记为素数的元素表示素数。
#includebool isPrime[N+1]; void sieveOfEratosthenes() { memset(isPrime, true, sizeof(isPrime)); isPrime[0] = isPrime[1] = false; for (int i = 2; i <= N; i++) { if (isPrime[i]) { for (int j = i*i; j <= N; j += i) { isPrime[j] = false; } } } }
方法 3：费马小定理
- 对于任意整数 a 和正整数 p，如果 a 不是 p 的倍数，则 a^(p-1) ≡ 1 (mod p)。
- 如果 a^(p-1) ≡ 1 (mod p) 成立，则 p 是素数。
bool isPrimeFermat(int n, int k) {
if (n <= 1) {
return false;
}
for (int i = 0; i < k; i++) {
int a = rand() % (n-1) + 1;
if (pow(a, n-1, n) != 1) {
return false;
}
}
return true;
} 
