Python使用穷举法求两个数的最大公约数问题

Python穷举法最大公约数 Python最大公约数 2022-12-20 12:12:19 878人浏览八月长安

Python 官方文档：入门教程 => 点击学习

摘要

目录使用穷举法求两个数的最大公约数穷举法求N个数的最大公约数和最小公倍数基本要求提高要求算法设计思路测试截屏总结使用穷举法求两个数的最大公约数 for m in range (0

使用穷举法求两个数的最大公约数

for m in range (0,2):
    a = int(input("请输入一个数:"))
    b = int(input("请输入另外一个数:"))
    #判断num1与num2的大小
    if a > b:
        #获取最小值
        min = b
    else:
        #获取最小值
        min = a
    for i in range(min+1,0,-1):    #倒序
        #满足公因数的条件:
        if (a % i == 0) and (b % i == 0):
            c = i
            break
    print('这两个数的最大公约数是:%d '%c)

穷举法求N个数的最大公约数和最小公倍数

基本要求

求N个数的最大公约数和最小公倍数。用C或c++或java或python语言实现程序解决问题。

提高要求

思考一个“求公约数”和“求公倍数”之类问题的“逆问题”，这个问题是这样的：已知正整数a0,a1,b0,b1，设某未知正整数x满足：

1、 x和a0的最大公约数是a1；

2、 x和b0的最小公倍数是b1。

Hankson的“逆问题”就是求出满足条件的正整数x。但稍加思索之后，他发现这样的x并不唯一，甚至可能不存在。因此他转而开始考虑如何求解满足条件的x的个数。

输入格式

输入第一行为一个正整数n，表示有n组输入数据。接下来的n行每行一组输入数据，为四个正整数a0，a1，b0，b1，每两个整数之间用一个空格隔开。输入数据保证a0能被a1整除，b1能被b0整除。

输出格式

输出共n行。每组输入数据的输出结果占一行，为一个整数。
对于每组数据：若不存在这样的x，请输出0；
若存在这样的x，请输出满足条件的x的个数；

样例输入

2

41 1 96 288

95 1 37 1776

算法设计思路

本程序先用穷举法计算两个数的最大公约数或最小公倍数。从两个数中较小数开始由大到小列举，直到找到公约数立即中断列举，得到的公约数便是最大公约数。

①定义1：对两个正整数a,b如果能在区间[a,0]或[b,0]内能找到一个整数temp能同时被a和b所整除，则temp即为最大公约数。

②定义2：对两个正整数a,b,如果若干个a之和或b之和能被b所整除或能被a所整除，则该和数即为所求的最小公倍数。

#include<stdio.h>
#define N 1000  
int input(int t[])
{
    int i,n;
    int k=1;
    printf("Please input the count of numbers(n>=2):"); 
    scanf("%d",&n);
    while(k)
    {
        printf("Please input numbers:\n");  
        for(i=0;i<n;i++)
        {
            scanf("%d",&t[i]);
        }
        k=exper(t,n);
    }
    return n;
}
int exper(int t[],int n)   
{
    int i;
    for(i=0;i<n;i++)
    {
        if(!t[i])
        {
            printf("error(输入为0)\n");
            return 1;
        }
    }
   return 0;
}
int divisor (int a,int b) 
{
    int  temp;          
    temp=(a>b)?b:a;    
    while(temp>0)
    {
       if (a%temp==0&&b%temp==0) 
          break;
       temp--;      
    }
  return (temp); 
}
int GCd(int t[],int n)
{
    int i;
    int c=t[0];
    for(i=1;i<n;i++)
    {
        c=divisor(c,t[i]);  
    }
    return c;
}
int multiple (int a,int b)
{
  int p,q,temp;
  p=(a>b)?a:b;   
  q=(a>b)?b:a;  
  temp=p;      
  while(1)   
  {
    if(p%q==0)
      break;  
    p+=temp;   
  }
  return  (p);
}
int Mul(int t[],int n)
{
    int i;
    int s=t[0];
    for(i=0;i<n;i++)
    {
        s=multiple(s,t[i]);  
    }
    return s;
}
int main()
{
 int t[N];
 int n;
 int flag=1;
 while(flag)
 {
    n=input(t);
    printf("The higest common divisor is %d\n",Gcd(t,n));  
    printf("The lowest common multiple is %d\n",Mul(t,n));
    printf("retreat:press 0\ncontiune:press 1");
    scanf("%d",&flag);
 }
 return 0;
}