How do I know if two numbers are relatively prime?

Question

I am trying to write a method that will calculate if two numbers are relatively simple to assign. I am primarily looking for answers on where to start. I know that there is a gcd() method that will do a lot for me, but the purpose pretty much forces me to do this without gcd or arrays.

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

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

Obviously, this method returns only true or false , because the main function will only print a specific line, depending on whether the two numbers are relatively prime or not.

I think I will probably have to write two for input4 , for both input5 and input5 , and maybe some if with the logical operand && , but I'm not sure

Answer 1

Well, if they are relatively simple, the greatest common factor is one, because - unless otherwise - both numbers can be divided by this number. Therefore, we only need an algorithm for calculating the largest common factor, for example, the Euclid method :

 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; } 

The Euclidean algorithm works in O (log n), which is thus faster than listing over all potential divisors that can be optimized to O (sqrt n).

Answer 2

Swift 4 response code @ 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 } 

Using

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

Answer 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 } } } 

I think this is a simple solution. Ask questions in the comments.