三个算法的C语言实现
欧几里得算法/辗转相除法
//欧几里得算法（辗转相除法）求最大公约数
#include <stdio.h>
#include <math.h>
void main()
{
int a,b,r,c,d; ////要求a和b的最大公约数，r是余数
printf("请输入两个数中较大的数a\n");
scanf("%d",&a);
c=a;
//判断a是否为正整数
if(a<0)
{
printf("请输入正整数");
printf("请输入两个数中较大的数a\n");
scanf("%d",&a);
c=a;
}
printf("请输入两个数中较小的数b\n");
scanf("%d",&b);
d=b;
//判断b是否为正整数
if(b<0)
{
printf("请输入正整数");
printf("请输入两个数中较小的数b\n");
scanf("%d",&b);
d=b;
}
while(r=a%b)
{
//将b当作新的a，r当作新的b
a=b;
b=r;
}
//程序结束的b就是最大公约数
printf("%d和%d的最大公约数是%d\n",c,d,b);
}
最小公倍数算法
//最小公倍数的加法方法
#include<stdio.h>
void main()
{
int a,b,c,d; //要求a和b的最小公倍数
printf("请输入两个数其中一个数a\n");
scanf("%d",&a);
c=a;
//判断a是否为正整数
if(a<=0)
{
printf("请输入正整数");
printf("请输入两个数其中一个数a\n");
scanf("%d",&a);
c=a;
}
printf("请输入两个数另外一个数b\n");
scanf("%d",&b);
d=b;
//判断b是否为正整数
if(b<=0)
{
printf("请输入正整数");
printf("请输入两个数另外一个数b\n");
scanf("%d",&b);
d=b;
}
while(a-b)
{
if(a>b)
{
b+=d;
}
else
{
a+=c;
}
}
printf("%d和%d的最小公倍数是%d\n",c,d,a);
}
乘法链算法
//乘法链算法
#include <stdio.h>
void main()
{
int u,s=1,t,a,n,m[30],i,c=0; //c为数组下标; //u是数字a的指数,s是计数,n是除数,t是根据0,1累乘的；
printf("请输入底数a\n");
scanf("%d",&a);
//判断a是否为正整数
if(a<0)
{
printf("请输入正整数");
printf("请输入底数a\n");
scanf("%d",&a);
}
printf("请输入除数n\n");
scanf("%d",&n);
//判断n是否为正整数
if(n<0)
{
printf("请输入正整数");
printf("请输入除数n\n");
scanf("%d",&n);
}
printf("请输入指数u\n");
scanf("%d",&u);
//判断u是否为正整数
if(u<0)
{
printf("请输入正整数");
printf("请输入指数u\n");
scanf("%d",&u);
}
//将指数u转换成二进制存入数组m[30]
while(u)
{
i=u%2;
m[c]=i;
c++;
u=u/2;
}
c--;//c代表存入数据长度 范围是0~c-1
for(;c>=0;c--)
{
printf("%d",m[c]);
}
printf("\n");
//开始进行乘法链算法
t=a;
for(;c>=0;c--)
{
t=(t*t)%n;
if(m[c])//如果二进制位是1则对s进行改变
{
s=(s*t)%n;
}
//如果二进制位是1则只对t进行乘方
}
printf("最后的结果是%d\n",s);
}
