C 语言求素数方法：暴力法：逐一检查每个数是否满足素数条件。埃拉托斯特尼筛法：创建一个数表，逐一筛除合数。Miller-Rabin 测试：使用费马小定理和欧拉准则判断素数。
如何用 C 语言求素数
素数，又称质数，是指大于 1 且只能被 1 和自身整除的自然数。用 C 语言求素数，主要有以下方法：
1. 暴力法
这种方法最简单，通过逐一检查每个数是否满足素数条件，来判断其是否为素数。实现代码如下：
立即学习“C语言免费学习笔记（深入）”；
#include int isPrime(int num) { if (num <= 1) { return 0; // 1 及以下不是素数 } for (int i = 2; i <= num / 2; i++) { if (num % i == 0) { return 0; // 不是素数 } } return 1; // 是素数}int main() { int num; printf("请输入一个整数："); scanf("%d", &num); if (isPrime(num)) { printf("%d 是素数n", num); } else { printf("%d 不是素数n", num); } return 0;}
2. 埃拉托斯特尼筛法
这种方法通过创建一张数表，并逐一筛除合数（非素数），来找出素数。实现代码如下：
#include #include int main() { int SIZE = 100; // 保存整数的数表大小 int *arr = (int *)malloc(SIZE * sizeof(int)); // 初始化数表，所有数都认为是素数 for (int i = 0; i < SIZE; i++) { arr[i] = 1; } // 从 2 开始，逐一筛除非素数 for (int i = 2; i < SIZE; i++) { if (arr[i]) { // 如果 i 是素数 for (int j = i * i; j < SIZE; j += i) { // 筛除 i 的倍数 arr[j] = 0; } } } // 打印素数 printf("素数列表："); for (int i = 2; i < SIZE; i++) { if (arr[i]) { printf("%d ", i); } } free(arr); return 0;}
3. Miller-Rabin 测试
这种方法通过使用费马小定理和欧拉准则，在一定概率下判断一个数是否为素数。实现代码较复杂，这里不再给出。
以上就是c语言怎么求素数的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/1437162.html
微信扫一扫 
支付宝扫一扫 
