我正在尝试编写一种方法,该方法将计算两个数字是否是赋值的相对质数。我主要是在寻找从哪里开始的答案。我知道有一种方法gcd()
可以为我做很多事情,但是赋值几乎使我不用gcd或数组就可以做到。
我有点开始了,因为我知道我将不得不在for循环中使用%
运算符。
public static boolean relativeNumber(int input4, int input5){
for(int i = 1; i <= input4; i++)
显然,此方法仅将返回
true
或false
,因为main
函数仅将打印特定的行,具体取决于这两个数字是否是相对质数。我在想我可能必须编写两个
for
循环,分别用于input4
和input5
,还可能需要编写带有逻辑if
操作数的某种&&
语句,但是我不确定。 最佳答案
好吧,如果它们是相对质数,则最大的公共(public)除数是1,因为-否则-两个数字都可以由该数字划分。因此,我们只需要一种算法来计算最大的公共(public)除法器,例如Euclid's method:
private static int gcd(int a, int b) {
int t;
while(b != 0){
t = a;
a = b;
b = t%b;
}
return a;
}
然后:
private static boolean relativelyPrime(int a, int b) {
return gcd(a,b) == 1;
}
Euclid算法在O(log n)中工作,因此比枚举所有可以优化为O(sqrt n)的潜在除数快得多。
关于java - 如何找出两个数字是否是质数?,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/28575416/