辅导笔记(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");

}