辅导笔记(1):最大公共素因子
辅导笔记(1):最大公共素因子
#include<iostream>
#include<stdio.h>
#include<math.h>
#define N 100
int prime(int k) //判断是否为素数
{
if(k<2)
{
return 0;
}
int p,i;
p=(int)sqrt(k);
for(i=2;i<=p;i++)
if(k%i==0)
{
return 0;
break;
}
return k;
}
int max(int *a,int k) //在一个数组中找到极大值
{
int maxm=a[0];
for(int i=0;i<k;i++)
{
if(a[i]>maxm)
maxm=a[i];
}
return maxm;
}
int main()
{
int m,n,k; // 定义两个正整数M和N；定义K为最大公共素因子
int i,j,d=0;//普通循环变量
int a[N],b[N],common[N]; //定义A为整数M的素因子数列，B为整数N的素因子数列，AB数列公共素因子的数列
scanf("%d %d",&m,&n); //输入整数M和N
//数组赋初值
for(i=0;i<N;i++)
{
a[i]=-1;b[i]=-1;common[i]=-1;
}
j=0; //j归零
for(i=2;i<=m;i++) //对于正整数M，求出其素因子序列（可能不止1个，存入数组a）
if(m%i==0&&prime(i)) //如果m能整除i，并且i是素数，记录i
{ a[j]=i;
// printf("%d\n",a[j]);
j++;
}
j=0;//j归零
for(i=2;i<=n;i++) //对于正整数n求出其素因子序列（可能不止1个，存入数组b）
{
if(n%i==0&&prime(i)) //如果n能整除i，并且i是素数，记录i
{
b[j]=i;
//printf("%d\n",i);
j++;
}
}
/*测试是否正确输出了素因子
for(j=0;j<N;j++)
printf("%2d ",a[j]) ;
printf("\n");
for(j=0;j<N;j++)
printf("%2d ",b[j]) ;
printf("\n");
*/
for(i=0;i<N;i++)
for(j=0;j<N;j++)
if(a[i]==b[j]&&a[i]>=2&&b[j]>=2) //找出a和b序列相同的素因子，可能不止1个，存入数组common
{
common[d]=a[i];
d++;
}
//输出最大的公共素因子
// for(i=0;i<N;i++)
//printf("%4d",common[i]);
if(max(common,d)==-1)
printf("0");
else
printf("\n%3d",max(common,d)); //调用数组求极大值的函数max
system("pause");
}
