如何找出两个数字是否是质数? [英] How to find out if two numbers are relatively prime?

问题描述

我正在尝试编写一种方法，该方法将计算两个数字是否相对于赋值而言是质数.我主要是在寻找从哪里开始的答案.我知道有一种方法 gcd()可以为我做很多事情，但是赋值几乎使我无需使用gcd或数组就可以做到这一点.

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.

我有点开始了，因为我知道我必须在for循环中使用％运算符.

I kind of have it started, because I know that I will have to use the % operator in a for loop.

public static boolean relativeNumber(int input4, int input5){
    for(int i = 1; i <= input4; i++)

很明显，此方法只会返回 true 或 false ，因为 main 函数仅根据是否输出来打印特定行这两个数字是否是相对质数.

Obviously this method is only going to return true or false because the main function is only going to print a specific line depending on if the two numbers are relatively prime or not.

我想我可能将不得不为 input4 和 input5 编写两个 for 循环，可能还需要编写一些带有逻辑&& 操作数的 if 语句，但我不确定.

I'm thinking I will probably have to write two for loops, both for input4, and input5, and possibly some kind of if statement with a logical && operand, but I'm not sure.

推荐答案

如果它们是相对质数，则最大的公共除数是一个，因为-否则，两个数字都可以由该数字划分.因此，我们只需要一种算法来计算最大的公共除数，例如 欧几里德方法 :

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:

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)的所有潜在除数要快得多..

Euclid's algorithm works in O(log n) which thus is way faster than enumerating over all potential divisors which can be optimized to O(sqrt n).

这篇关于如何找出两个数字是否是质数?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！