精华内容
下载资源
问答
  • 两个整数的最大公约数 文章目录两个整数的最大公约数1. 欧几里得算法2. 连续整数检测算法3. 求m、n的质因数 1. 欧几里得算法 gcd(m,n)=gcd(n,m mod n) 假设x是m,n的最大公约数,且m大于n(m小于n时,上式实现两个...

    两个整数的最大公约数

    1. 欧几里得算法

    gcd(m,n)=gcd(n,m mod n)

    假设x是m,n的最大公约数,且m大于n(m小于n时,上式实现两个数的交换)

    m=(m/n)*n+m%n( / 表示整除)

    n=(n/x)*x

    则,则(m/n)*n有约数x,又m有约数x,则m%n也可以被x整除

    #include <iostream>
    using namespace std;
    int Euclid(int m, int n)
    {
        while (n)
        {
            int t = m % n;
            m = n;
            n = t;
        }
        return m;
    }
    int main()
    {
        cout << Euclid(60, 24) << endl;
    }
    

    2. 连续整数检测算法

    从m、n中较小的数开始查找,直到找到可以被m、n都整除的数

    #include <iostream>
    using namespace std;
    int gcd(int m, int n)
    {
        int t = min(m, n);
        while (m % t != 0 || n % t != 0)
            --t;
        return t;
    }
    int main()
    {
        cout << gcd(60, 24) << endl;
    }
    

    3. 求m、n的质因数

    abc

    算法设计与分析基础(ch1)

    求不大于整数n的连续质数序列:

    埃拉托色尼筛选法(sieve of Eratosthenes)

    #include <iostream>
    #include <vector>
    using namespace std;
    //埃拉托色尼筛选法,产生一个不大于给定整除n的连续质数序列
    void Sieve(int n, vector<int> &isPrime)
    {
        for (int i = 2; i * i <= n; ++i)
        {
            if (isPrime[i])
            {
                int t = i * i;
                while (t <= n)
                {
                    isPrime[t] = 0;
                    t = t + i;
                }
            }
        }
    }
    int gcd(vector<int> &isPrime, int m, int n)
    {
        int result = 1;
        for (int i = 2; i <= n; ++i)
        {
            //如果i是质数
            if (isPrime[i])
            {
                while (m % i == 0 && n % i == 0)
                {
                    m = m / i;
                    n = n / i;
                    result *= i;
                }
            }
        }
        return result;
    }
    int main()
    {
        int m, n;
        cin >> m >> n;
        vector<int> isPrime(min(m, n) + 1, 1); //记录较小数的质数序列
        // cout << isPrime.size() << endl;
        Sieve(min(m, n), isPrime);
        cout << gcd(isPrime, max(m, n), min(m, n)) << endl;
    }
    
    展开全文
  • java两个整数的最大公约数,最简单的方式
  • 主要介绍了php计算两个整数的最大公约数常用算法,实例总结了求最大公约数的三种常用方法,具有一定参考借鉴价值,需要的朋友可以参考下
  • 两个整数的最大公约数 import java.util.Scanner; public class ZuiDaGongYueShu { public static void main(String[] args) { Scanner sc=new Scanner(System.in); System.out.print("请输入两个整数用来求...
    求两个整数的最大公约数
    import java.util.Scanner;
    
    public class ZuiDaGongYueShu {
      public static void main(String[] args) {
       Scanner sc=new Scanner(System.in);
    
       System.out.print("请输入两个整数用来求最大公约数:");
       int a=sc.nextInt();
       int b=sc.nextInt();
       int min,c=0;
       if(a>b) min=b; else min=a;
       for(int i=1;i<=min;i++) {
        if(b%i==0&&a%i==0) {
         c=i;
        }
        }
       System.out.println("这两个数的最大公约数为:"+c);
      }
    }
    
    结果显示:
    请输入两个整数用来求最大公约数:15 25
    这两个数的最大公约数为:5
    求两个整数的最小公倍数
    import java.util.Scanner;
    
    public class ZuiXiaoGongBeiShu {
      public static void main(String[] args) {
       Scanner sc=new Scanner(System.in);
       
       System.out.print("请输入两个整数用来求最小公倍数:");
       int a=sc.nextInt();
       int b=sc.nextInt();
       int max,c=0;
       if(b>a) max=b; else max=a;
       for(int i=max;i>=max;i++) {
        if(i%b==0&&i%a==0) {
         c=i;  break;
        }
       }
       System.out.println("这两个数的最小公倍数为:"+c);
      }
    }
    
    结果显示:
    请输入两个整数用来求最小公倍数:15 25
    这两个数的最小公倍数为:75
    求最大公因数与最小公倍数存在公式法
    import java.util.Scanner;
    
    public class ZuiDaGongYueShu2 {
      public static void main(String[] args) {
       Scanner sc=new Scanner(System.in);
       
       System.out.print("请输入两个整数用来求最大公约数:");
       int a=sc.nextInt();
       int b=sc.nextInt();
       if(a<b) {
        int t=a;
        a=b;
        b=t;//此时b为最小的数
       }
       int i;
       for(i=b;i>0;i--)
       if(b%i==0&&a%i==0) {
         break;
        }
       System.out.println("这两个数的最大公约数为:"+i);
       
       //有一个公式  最小公倍数=a*b/最大公约数
       int k=a*b/i;
       System.out.println("这两个数的最小公倍数为:"+k);
      }
    }
    
    结果显示:
    请输入两个整数用来求最大公约数:15 20
    这两个数的最大公约数为:5
    这两个数的最小公倍数为:60
    展开全文
  • /*** 求两个的最大公约数和最小公倍数* @author kele**/public class GongyueGongbeiShu {/*** 求两个的最大公约数* @param m* @param n* @return*/public static int MaxGys(int m,int n) {int r;whi...

    共回答了19个问题采纳率:89.5%

    package com.fmzrt;

    /**

    * 求两个数的最大公约数和最小公倍数

    * @author kele

    *

    */

    public class GongyueGongbeiShu {

    /**

    * 求两个数的最大公约数

    * @param m

    * @param n

    * @return

    */

    public static int MaxGys(int m,int n) {

    int r;

    while(n != 0) {

    r = m % n;

    m = n;

    n = r;

    }

    return m;

    }

    /**

    * 求两个数的最小公倍数

    * @param m

    * @param n

    * @return

    */

    public static int MinGbs(int m,int n) {

    return m * n / MaxGys(m,n);

    }

    public static void main(String[] args) {

    System.out.println("最大公约数 :(36,12) = " + GongyueGongbeiShu.MaxGys(36,12));

    System.out.println("最小公倍数 :(36,12) = " + GongyueGongbeiShu.MinGbs(36,12));

    }

    }

    1年前

    3

    展开全文
  • /*求两个整数的最大公约数*/ /* 两个整数的最大公约数是能够同时整除他们的最大正整数。可以用辗转相除法,又称欧几里得算法。 原理如下:两个整数的最大公约数等于其中较小的数和两数的相除余数的最大公约数。 算法...
    /*求两个整数的最大公约数*/
    /*
    两个整数的最大公约数是能够同时整除他们的最大正整数。可以用辗转相除法,又称欧几里得算法。
    原理如下:两个整数的最大公约数等于其中较小的数和两数的相除余数的最大公约数。
    算法思想如下:
    (1)对于已知的两个数m、n,使m>n;
    (2)m除以n的余数r;
    (3)若r=0,则为求得的最大公约数,算法结束;否则执行(4);
    (4)m=n,n=r,重复执行(2);
    */
    #include <stdio.h>
    int main() 
    {
    	int m,n;
    	int r;
    	printf("请输入两个整数:\n");
    	scanf("%d %d",&m,&n);
    	r = m%n;
    	while(r!=0){
    		m=n;
    		n=r;
    		r=m%n; 
    	} 
    	printf("最大公约数为%d",n);
    }
    
    
    
    展开全文
  • 程序实现的功能:从键盘输入两个整数,输出两个整数的最大公约数。 基本思路:可采用辗转相除法,辗转相减法,穷举法对两个整数求最大公约数,并且要对负数、0单独考虑。 (1)可以先对负数求绝对值,转换成正数,...
  • 两个整数的最大公约数和最小公倍数的C语言方法
  • 计算两个整数的最大公约数 【 最大公约数(即能同时整除m和n的最大正整数)】 1.欧几里德算法描述 算法1:辗转相除法: 第1步:读入两个正整数m和n,大的数存入m,小的数存入n; 第2步:求m除以n的余数r; 第3步:...
  • Python中用辗转相除法求两个整数的最大公约数和最小公倍数 首先,得到两个已知的正整数m、n,使得m > n(这里可以通过if语句判断m、n的大小,然后用三条语句使得m > n)例如: if m < n: t = n n = m m ...
  • **练习要求:生成两个0~100(包含0和100)的随机整数m和n,求这两个整数的最大公约数和最小公倍数 求两个整数的最大公约数和最小公倍数,需要用到“辗转相除法” 辗转相除法: 1.先比较两个整数大小,使得m>n 2....
  • 笔试题 ----求两个整数的最大公约数和最小公倍数 使用辗转相除法可以快速的实现求最大公约数,而最小公倍数可以通过最大公约数求出。 import java.util.Scanner; /** * 求两个整数的最大公约数和最小公倍数 * @...
  • 获取两个整数,求出这两个整数的最大公约数和最小公倍数。最大公约的计算一般使用辗转相除法,最小公倍数啧使用两个数的乘积除以最大公约数 x=int(input('请输入一个整数:')) y=int(input('请输入一个整数:')) m=x...
  • Java代码求两个整数的最大公约数和最小公倍数。 ** 发布的第二篇博文,希望大家多多支持!!! 用java代码求两个整数的最大公约数和最小公倍数首先要明白如何求最大公约数和最小公倍数,背后的算法是什么. 1.首先需要写一...
  • #获取两个整数,求这两个整数的最大公约数和最小公倍数。最大公约数计算一般使用辗转相除法,最小公倍数计算则使用两个数##的乘积除以最小公倍数。 s1=int(input("请输入第一个整数:")) s2=int(input("请输入第二个...
  • 从键盘接收两个整数,编写程序求出这两个整数的最大公约数和最小公倍数(提示:求最大公约数可用辗转相除法,求最小公倍数则用两数的积除以最大公约数即可)。 实现代码如下: import java.util.Scanner; public class ...
  • /** *递归实现两个整数的最大公约数 */ #include<stdio.h> intgcd(intm,intn); intmain(void) { intm,n,temp; printf("输入两个整数:\n"); while((sca...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 6,133
精华内容 2,453
关键字:

两个整数的最大公约数