2つの正の整数mとnを渡すと、mとnが共にプライムである場合に真を返す方法を書いてください。 2つの整数は、正の整数の共通の除数が1でないときには、互いに素である。2つの整数が互いに素であることを示すコードを作成するにはどうすればよいですか？
m≦nと仮定できます。ここで
public static boolean coPrime(int m, int n) {
if (m%n == 0){
return true;
}
return false;
}
私がこれまで持っているものです。 あなたは彼らが共生していることをどのように認識していますか？
/* The running time of the function is O(m) - linear */
public static boolean coPrime(int m, int n) {
/* Since m <= n */
int index = 2;
bool is_coprime = true;
while(index <= m){
if(m % index == 0 and n % index == 0){
is_coprime = false;
}
index = index + 1;
}
return is_coprime;
}
iがmとnは1よりも大きくなる。しかし、Mならば、nはあなたが1に等しくすることができると仮定しm、nは両方ともあなたはあなたが無限ループを持っているので、 'ループ内index'をインクリメントすることを怠ってきた1 –
に割り切れるとなりますので、その場合を避けるために、条件（インデックス！= 1）を追加することができます。また、m == n == 1の場合、定義1と1が共起するため、変更は必要ありません。最後に、このアルゴリズムは、ユークリッドのアルゴリズムの様々な変種に比べて非常に非効率的です。しかし、それはOPが最初のスタートとして自分で出ているべきかの良い例です。 –
彼らのGCDが1
ユークリッドのアルゴリズムは、二つの整数間のGCDを見つけるための非常にシンプルかつストレートフォワードである場合は、二つの数が互いに素ている知っている：だから
private int gcd(int p, int q) {
if (q == 0) {
return p;
}
return gcd(q, p % q);
}
すべてのあなた次のような2つの整数でこのメソッドを呼び出します。
private boolean coprime(int p, int q) {
return (gcd(p, q) == 1);
}
'return BigInte ger.valueOf（M）.gcd（BigInteger.valueOf（N））に等しい（BigInteger.ONE）; ' – Andreas