大学计算机基础C语言实验习题选（1）实验4-3 循环结构-判素数四种做法 Miller-Rabin素性测试孪生素数（6倍数判别法）朴素做法朴素改进

本文主要是介绍大学计算机基础C语言实验习题选（1）实验4-3 循环结构-判素数四种做法 Miller-Rabin素性测试孪生素数（6倍数判别法）朴素做法朴素改进，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

实验4-3 循环结构-判素数

编写程序sushu.c，输入一个正整数n(n>2)，判断n是否为素数。

格式要求输入：scanf("%d",&n) 输出： (1)如果n<=2，则printf(“ERROR”)
(2)如果是素数，则printf("%d是素数", n) 否则printf("%d不是素数", n)

保存，编译、运行、测试成功后将源程序文件（.c或.cpp）压缩，提交。

方法一朴素做法

时间复杂度：O（n）
直接一个一个筛

#include<stdio.h>
int main()
{int n;scanf("%d",&n);if(n<=2){printf("ERROR");}else{bool is_prime=true;for(int i=2;i<n;i++){if(n%i==0){is_prime=false;}}if(is_prime){printf("%d是素数",n);}else{printf("%d不是素数",n);}}return 0;
}

方法二：方法一改进

时间复杂度：O（根号n）
如果是偶数，且不是2，肯定不是素数
想象因式分解。3*4=12，不必要从2一直筛到n-1，直接筛到即可
这里最好不要用sqrt函数，计算机中，平方运算所需cpu周期比根号少得多，故更快些

#include<stdio.h>
int main()
{int n;scanf("%d",&n);if(n<=2){printf("ERROR");}else if(n%2==0&&n!=2){printf("%d不是素数",n);}else{bool is_prime=true;for(int i=2;i*i<=n;i++){if(n%i==0){is_prime=false;}}if(is_prime){printf("%d是素数",n);}else{printf("%d不是素数",n);}}return 0;
}

方法三：6倍数判别法

时间复杂度：O（根号n）是松的时间复杂度，实际上比上一个快2-4倍
这里有一个数学定理:大于等于5的质素一定和6的倍数相邻
详细解答请转步知乎
如何证明大于等于5的质素一定和6的倍数相邻？
其实就是孪生质数，有兴趣的读者可以去网上搜索了解

#include<stdio.h>
int main()
{int n;scanf("%d",&n);if(n<=2){printf("ERROR");}else if(n%2==0&&n!=2){printf("%d不是素数",n);}else{int i,is_prime=1;if(n%6!=1&&n%6!=5){is_prime=0;}else{for(i=5;i*i<=n;i+=6){if(n%i==0||n%(i+2)==0){is_prime=0;}}}if(is_prime){printf("%d是素数",n);}else{printf("%d不是素数",n);}}return 0;
}

方法四：Miller-Rabin素性测试

采用了随机抽样测试的方法，实际上有可能会判不准，因为费马小定理的逆命题实际上是错的，但是其发生概率实际很低

在测试质数时，抽样法是一个非常有用的工具。下面给出一种质数判定方法：
对于待判定的整数n。设n－1＝d×2s（d是奇数）。对于给定的基底a，若ad≡1 (mod n)，或存在0≤r<s使a≡－1 (mod
n)，则称n为以a为底的强伪质数。利用二分法，可以在O(logn)的时间内判定n是否为以a为底的强伪质数。
对于合数c，以小于c的数为底，c至多有1/4的机会为强伪质数。

如果不是随机抽样，而是抽样特殊情况——最小的几个质数，则：如果只用2一个数进行测试，最小的强伪质数（反例）是2047，所以一个数显然不够；
如果用2和3两个数进行测试，最小的强伪质数为1373653，大于106；
如果用2,3,5进行测试，最小的强伪质数为25326001，大于2×107；
如果用2,3,5,7进行测试，最小的强伪质数为3215031751，大于3×109，已经比32位带符号整数的最大值还大了。
可见，通常只要抽取2,3,5,7这几个固定的数进行测试就能保证测试的正确性了。

适用于大数素性判断，用到了费马小定理
感兴趣的读者可以看以下两篇文章
Miller-Rabin素性测试算法详解
素数与素性测试（Miller-Rabin测试
这在ACM中有可能会遇到，杀鸡焉用牛刀，上面三种交学校的实验够用了
这里用C语言实现

#include<stdio.h>
typedef long long ll;
ll pow_mod(ll a,ll b,ll r)
{ll ans=1,buff=a;while(b){if(b&1){ans=(ans*buff)%r;}buff=(buff*buff)%r;b>>=1;}return ans;
}
ll test(ll n,ll a,ll d)
{if(n==2){return 1;}if(n==a){return 0;}if(d%2==0){d>>=1;}int t=pow_mod(a,d,n);while(d!=n-1&&t!=n-1&&t!=1){t=t*t%n;d<<=1;}return t==n-1||(d&1)==1;
}
ll isprime(ll n)
{int a[]={2,3,5,7};for(int i=0;i<=3;i++){if(n==a[i]){return 1;}if(!test(n,a[i],n-1)){return 0;}}
}
int main()
{int n;scanf("%d",&n);if(n<=2){printf("ERROR");}else if(n%2==0&&n!=2){printf("%d不是素数",n);}else{if(isprime(n)){printf("%d是素数",n);}else{printf("%d不是素数",n);}}return 0;
}