Euclid, Prime numbers, and the Inclusion-Exclusion Principle

Harder, Better, Faster, Stronger

The Euclidean algorithm, the algorithm to compute the greatest common divisor, or $latex \gcd$, of two numbers, dates back to antiquity (obviously). We can use it to make a fast test for primality, at least up to some confidence—and that’s where the inclusion-exclusion principle comes in.


Let us begin by the Euclidean algorithm. Originally, the algorithm was done by successive subtraction (and becomes quickly tedious as numbers grow), but the modern version, at least the one that I know of, uses divisions and remainders (modulo), and computes the $latex \gcd(a,b)$ of two numbers $latex a$ and $latex b$ in $latex O(\lg\min(a,b))$ (counting division as an $latex O(1)$ operation), which is very fast.

View original post 622 more words

About Khuram Ali

Programming... Programming and Programming...!!!

Posted on June 3, 2013, in Data Structures, Programming and tagged , , . Bookmark the permalink. Leave a comment.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: