C 语言中检查素数的方法有三种：暴力算法：遍历从 2 到平方根的所有整数，若能整除则非素数。费马小定理：a^(p-1) % p = 1，若恒等则为素数。Miller-Rabin 算法：更有效，但实现较复杂。
如何在 C 语言中检查素数
什么是素数？
素数是指除自身和 1 之外，不能被其他正整数整除的自然数。
C 语言中检查素数的方法
1. 暴力算法
立即学习“C语言免费学习笔记（深入）”；
遍历从 2 到 待检测数的平方根的所有整数。如果待检测数能被遍历的整数整除，则它不是素数。如果待检测数无法被任何遍历的整数整除，则它是一个素数。
代码实现：
#include #include
2. 费马小定理
对于任何素数 p 和任何整数 a，a^(p-1) % p = 1。
代码实现：
#include int is_prime(int num) { if (num <= 1) return 0; for (int i = 2; i < num; i++) { if (pow(i, num-1) % num != 1) return 0; } return 1;}
3. Miller-Rabin 算法
这是检查素数的一种更有效的算法，但实现起来比较复杂。
代码实现：
#include #include #include int is_prime(int num) { if (num <= 1) return 0; if (num <= 3) return 1; if (num % 2 == 0 || num % 3 == 0) return 0; int s = 0; uint64_t d = num-1; while (d % 2 == 0) { s++; d /= 2; } for (int i = 0; i < 20; i++) { int a = rand() % (num-1) + 1; uint64_t x = powmod(a, d, num); if (x == 1 || x == num-1) continue; int j = 1; while (j < s && x != num-1) { x = powmod(x, 2, num); if (x == 1) return 0; j++; } if (x != num-1) return 0; } return 1;}
以上就是c语言怎么检验是不是素数的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/1452357.html
微信扫一扫 
支付宝扫一扫 
