java如何判断两大整数是否互质，希望有高效点的方法

Question

如题，做做rsa算法，遇到这个问题，希望有同行指点，谢谢

Answer 1

产生大素数吗？可以用Miller检验算法

Answer 2

public class CheckNumber {
  public static void check(int m,int n){
    int k=0;
    for(k = m;0 != k%n;k+=m);   
    if(k==m*n){
      System.out.print(m+"与"+n+"为互质数");
    }else{
      System.out.print(m+"与"+n+"不为互质数");
    }
  }
  
  public static void main(String[] args) {
    check(36,7);
  }
}
应该差不多吧 楼主可以试着将check();的参数换一下 换成你想验证的2个数

Answer 3

刚写了一个：
  public boolean check(int m, int n)
  {
  return check2(m > n ? m : n, m <= n ? m : n);
  }   public boolean check2(int max, int min)
  {
  int mo = max % min;
  if (mo == 0) {
  return min == 1 ? true : false;
  }
  else {
  return check2(min, mo);
  }
  }

Answer 4

WIN_ANGEL(WIN_ANGEL) 你写的有问题，可能溢出，并且计算量太大

Answer 5

redduke1202(勿以分少而不回★★勿以分多而灌水) ( ) 信誉：100    Blog   加为好友  2007-04-18 14:13:10  得分: 0  
 
 
   好像有个相减来判断的
  
 
----------------------------
广义欧几里德除法 :)

Answer 6

HOHO~ CrazyGou(阿狗)(简单就是美) 你用的是递归计算 大数除以小数的 余数和小数比较 如果他们互质那 大数和小数就互质 的方法吧 我也意识到了我上面那程序的不足 本来也想按你用的那个方法写一个呢 你下手还真快 HOHO~ 既然你写了我就不写了 这也是我能想到的最好的方法了 继续看看还有没有高人给出更高效的算法

Answer 7

楼主 CrazyGou(阿狗)的算法还是不错的 在判断两个数是否互质的很多方法中 “大数除以小数的 余数和小数比较 如果他们互质那 大数和小数就互质” 这个方法算是最简单的了 楼主如果有什么高招欢迎帖出来让大家学习一下