C语言 大数判断素数运算
发布网友
共3个回答
热心网友
下面的算法是判断int范围内的数字是否是素数的。可以改造一下，改成高精度的，就可以判断50位以上的数字了。
//参数入口为test(lld n)
typedef __int lld;
const lld MAX=10;
lld multi(lld a,lld b,lld m)//加法代替乘法，防止溢出__int
{
lld ret=0;
a%=m;
while(b)
{
if(b&1) if((ret+=a)>=m) ret-=m;
if((a<<=1)>=m) a-=m;
b>>=1;
}
return ret;
}
lld mod(lld a,lld b,lld m)
{
lld x,y;
if(b==1)//1次幂，直接返回
return a%m;
x=mod(a,b>>1,m);//二分求幂
y=multi(x,x,m);//平方一下
if(y==1&&x!=1&&x!=m-1)//如果结果是1的时候，如果x不是1而且不是m-1那么m必然不是素数。
return 0;
if(b&1)//奇数的情况，再乘上一个a
y=multi(y,a,m);
return y;
}
lld gen(lld m)
{
lld ret=1,i;
for(i=0;i<4;i++)
ret*=rand();
ret%=m;
if(ret<0)
ret+=m;
return ret;
}
//入口
bool test(lld n)
{
lld a,i,tmp;
if(n<2)//小于2不是素数
return 0;
if(n==2)//2是素数，直接返回
return 1;
if((n&1)==0)//偶数
return 0;
for(i=0;i<MAX;i++)//测试最大次数
{
a=gen(n-1)+1;//生成一个2到n-2的数字
tmp=mod(a,n-1,n);//快速幂
if(tmp!=1)//结果不是1，不是素数
return 0;
}
return 1;//是素数
}
int main()
{
lld n;
scanf("%Id",&n);
if(test(n))puts("YES");
else puts("NO");
return 0;
}
热心网友
#include <stdio.h>
int main(){
int a=0; // 素数的个数
int num=0; // 输入的整数
printf("输入一个整数：");
scanf("%d",&num);
for(int i=2;i<num;i++)
{
if(num%i==0){
a++; // 素数个数加1
}
}
if(a==0)
{
printf("%d是素数。\n", num);
}else
{
printf("%d不是素数。\n", num);
}
return 0;
}
(将其要判断的大数输进去，按回车键就可得出结论)
热心网友
考虑有字符串实现吧
