Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

What is the fastest way to check if two given numbers are coprime?

One way is to calculate their gcd and check if it is 1.

Is there some faster way?

like image 542
Lazer Avatar asked Sep 27 '09 11:09

Lazer


People also ask

How do you check if two numbers are Coprime?

Co-prime numbers or relatively prime numbers are those numbers that have their HCF (Highest Common Factor) as 1. In other words, two numbers are co-prime if they no common factor other than 1.

How do you know if something is a Coprime?

Two integers are relatively prime or Coprime when there are no common factors other than 1. This means that no other integer could divide both numbers evenly.


2 Answers

if you're running on a machine for which division/remainder is significantly more expensive than shifts, consider binary GCD.

like image 44
Jason S Avatar answered Dec 02 '22 01:12

Jason S


The Euclidean algorithm (computes gcd) is very fast. When two numbers are drawn uniformly at random from [1, n], the average number of steps to compute their gcd is O(log n). The average computation time required for each step is quadratic in the number of digits.

There are alternatives that perform somewhat better (i.e., each step is subquadratic in the number of digits), but they are only effective on very large integers. See, for example, On Schönhage's algorithm and subquadratic integer gcd computation.

like image 168
jason Avatar answered Dec 02 '22 01:12

jason