CODEWITHSUNDEEP
algorithmnumber-theorygreatest-common-divisor
Lazer
Lazer

Reputation: 94920

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?

Upvotes: 11

Views: 14134

Answers (2)

Jason S
Jason S

Reputation: 189796

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

Upvotes: 7

jason
jason

Reputation: 241701

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.

Upvotes: 13

Related Questions