Java 如何判断两个数是否互质？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/28575416/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
How to find out if two numbers are relatively prime?
提问by Tony
I'm trying to write a method that will calculate if two numbers are relatively prime for an assignment. I'm primarily looking for answers on where to start. I know there is a method gcd()that will do a lot of it for me, but the assignment is pretty much making me do it without gcd or arrays.
我正在尝试编写一种方法来计算两个数字是否是赋值的素数。我主要是在寻找关于从哪里开始的答案。我知道有一种方法gcd()可以为我做很多事情，但是这个任务几乎让我在没有 gcd 或数组的情况下做到了。
I kind of have it started, because I know that I will have to use the %operator in a for loop.
我有点开始了，因为我知道我将不得不%在 for 循环中使用运算符。
public static boolean relativeNumber(int input4, int input5){
for(int i = 1; i <= input4; i++)
Obviously this method is only going to return trueor falsebecause the mainfunction is only going to print a specific line depending on if the two numbers are relatively prime or not.
显然，这个方法只会返回，true或者false因为该main函数只会根据两个数字是否互质来打印特定的行。
I'm thinking I will probably have to write two forloops, both for input4, and input5, and possibly some kind of ifstatement with a logical &&operand, but I'm not sure.
我想我可能不得不写两个for循环，分别是 forinput4和input5，可能还有某种if带有逻辑&&操作数的语句，但我不确定。
采纳答案by Willem Van Onsem
Well in case they are relatively prime, the greatest common divider is one, because - if otherwise - both numbers could be devided by that number. So we only need an algorithm to calculate the greatest common divider, for instance Euclid's method:
好吧，如果它们是素数，则最大的除法器是 1，因为 - 如果不是 - 两个数字都可以除以该数字。所以我们只需要一个算法来计算最大公约数，例如欧几里德的方法：
private static int gcd(int a, int b) {
int t;
while(b != 0){
t = a;
a = b;
b = t%b;
}
return a;
}
And then:
进而：
private static boolean relativelyPrime(int a, int b) {
return gcd(a,b) == 1;
}
Euclid's algorithmworks in O(log n)which thus is way faster than enumerating over all potential divisors which can be optimized to O(sqrt n).
Euclid 的算法在O(log n) 中工作，因此比枚举可以优化为O(sqrt n) 的所有潜在除数快得多。
回答by BSeitkazin
package stack;
import java.util.Scanner; //To read data from console
/**
*
* @author base
*/
public class Stack {
/**
* @param args the command line arguments
*/
public static void main(String[] args) {
Scanner in = new Scanner(System.in); // with Scanner we can read data
int a = in.nextInt(); //first variable
int b = in.nextInt(); //second variable
int max; // to store maximum value from a or b
//Let's find maximum value
if (a >= b) {
max = a;
} else {
max = b;
}
int count = 0; // We count divisible number
for (int i=2; i<=max; i++) { // we start from 2, because we can't divide on 0, and every number divisible on 1
if (a % i == 0 && b % i==0) {
count++; //count them
}
}
if (count == 0) { // if there is no divisible numbers
System.out.println("Prime"); // that's our solutions
} else {
System.out.println("Not Prime"); //otherwise
}
}
}
I think that, this is the simple solution. Ask questions in comments.
我认为，这是简单的解决方案。在评论中提问。
回答by Celil Bozkurt
Swift 4code for @williem-van-onsem answer;
@williem-van-onsem 答案的Swift 4代码；
func gcd(a: Int, b: Int) -> Int {
var b = b
var a = a
var t: Int!
while(b != 0){
t = a;
a = b;
b = t%b;
}
return a
}
func relativelyPrime(a : Int, b: Int) -> Bool{
return gcd(a: a, b: b) == 1
}
Usage;
用法;
print(relativelyPrime(a: 2, b: 4)) // false
