fastest method to determine if two numbers are coprime?

Question

I am working on a mathematical problem that involves coprime integers. I wrote a computer program that allows me to search for the numbers I am looking for. However I am looking at a large set of integers and I have to compare many pairs of numbers and determine if they are coprime. My program has to do this so many times that any reduction in the calculation time for each pair of numbers would significantly reduce the overall run time of the program. I am currently using the Euclidean algorithm. http://en.wikipedia.org/wiki/Euclidean_algorithm Even though the Euclidean algorithm is a very efficient method, I don't know if it's the fastest. I don't need the gcd of the two numbers I just need to determine if they are coprime or not. My pseudocode: **while** (B ≠ 0) {T = B B = A mod T A = T} where A and B are the pair of integers in question and T is a dummy variable used to hold a value to be used in a later calculation. For those who haven't written a computer program before, **while** means that the process in the brackets will repeat until the condition in the parentheses is false. At the end of the loop the variable A becomes the gcd of the original two integers. if A=1 the two numbers are coprime if A>1 then the numbers are not coprime. Even though the program above is simple, it is an iterative process and I'm looking for a method that only needs one or two steps. Thanks in advance!

Answer 1

There are two method for finding the Greatest Common Factor:

(1) factor trees

(2) Euclid's method

It will take more than 2 steps to factor a number alone...

Stick with Euclid's method.