Как узнать, являются ли два числа относительно простыми?

Я пытаюсь написать метод, который будет вычислять, если два числа являются относительно простыми для назначения. Я в первую очередь ищу ответы о том, с чего начать. Я знаю, что есть метод 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 с логическим операндом &&, но я не уверен ,

Ответы

Ответ 1

Хорошо, если они относительно простые, наибольший общий делитель - один, потому что - если иначе - оба числа могут быть разделены на это число. Поэтому нам нужен только алгоритм вычисления наибольшего общего делителя, например Euclid 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;
}

Алгоритм Евклида работает в O (log n), который, таким образом, быстрее, чем перечисление по всем потенциальным делителям, которые могут быть оптимизированы до O (sqrt n).

Ответ 2

Swift 4 код для ответа @williem-van-onsem;

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
}

Использование

print(relativelyPrime(a: 2, b: 4)) // false

Ответ 3

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 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 our solutions
        } else {
            System.out.println("Not Prime"); //otherwise
        }
    }
}

Я думаю, что это простое решение. Задавайте вопросы в комментариях.