C 语言中计算素数的方法有三种：遍历法、埃拉托斯特尼筛法和费马小定理。遍历法逐个遍历整数，检查是否仅被 1 和自身整除。埃拉托斯特尼筛法用布尔数组标记素数，将非素数倍数标记为非素数。费马小定理基于数学定理，通过检验随机整数的指数运算结果来判断素数。
C语言中计算素数的方法
素数定义：
素数是指仅被 1 和自身整除的正整数（不包含 1）。
C语言中计算素数的方法：
方法 1：遍历法
立即学习“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 的倍数标记为非素数。在遍历结束后，数组中标记为素数的元素表示素数。
#include bool 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;}
以上就是C语言素数怎么算的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/1452397.html
微信扫一扫 
支付宝扫一扫 
