highest common factor-fewest iterations
Along similar lines to Ilmari's solution, but slightly shorter (comparing expanded versions):

#include &lt;stdlib.h&gt;
#include &lt;stdio.h&gt;

#define D(pn, p) (a%(pn) + b%(pn) ? 1 : (p))
#define P(p) D(p, p)
#define P2(p) D(p, p) * D(p*p, p)

int main (int argc, char *argv[]) {
    int a, b, t, gcd;
    if (argc != 3) return 1;

    a = atoi(argv[1]);
    b = atoi(argv[2]);
    if (a &lt; 1 || a &gt; 5000 || b &lt; 1 || b &gt; 5000) return 1;

    // Force an order: a &lt;= b
    if (a &gt; b) {
        t = a; a = b; b = t;
    }

    gcd = (a == b || a*2 == b || a*3 == b || a*4 == b || a*5 == b ||
           a*3 == b*2 || a*5 == b*2 || a*4 == b*3 || a*5 == b*3 ||
           a*6 == b*5) ? a :
            ((a|b) &amp; -(a|b)) *
            P(3) * D(9, 3) * D(27, 3) * D(81, 3) * D(243, 3) * D(729, 3) *
            P(5) * D(25, 5) * D(125, 5) * D(625, 5) *
            P(7) * D(49, 79) * D(343, 7) *
            P2(11) * P2(13) * P2(17) * P2(19) * P2(23) *
            P(29) * P(31) * P(37) * P(41) * P(43) * P(47) * P(53) * P(59) *
            P(61) * P(67) * P(71) * P(73) * P(79) * P(83) * P(89) * P(97) *
            P(101) * P(103) * P(107) * P(109) * P(113) * P(127) * P(131) *
            P(137) * P(139) * P(149) * P(151) * P(157) * P(163) * P(167) *
            P(173) * P(179) * P(181) * P(191) * P(193) * P(197) * P(199) *
            P(211) * P(223) * P(227) * P(229) * P(233) * P(239) * P(241) *
            P(251) * P(257) * P(263) * P(269) * P(271) * P(277) * P(281) *
            P(283) * P(293) * P(307) * P(311) * P(313) * P(317) * P(331) *
            P(337) * P(347) * P(349) * P(353) * P(359) * P(367) * P(373) *
            P(379) * P(383) * P(389) * P(397) * P(401) * P(409) * P(419) *
            P(421) * P(431) * P(433) * P(439) * P(443) * P(449) * P(457) *
            P(461) * P(463) * P(467) * P(479) * P(487) * P(491) * P(499) *
            P(503) * P(509) * P(521) * P(523) * P(541) * P(547) * P(557) *
            P(563) * P(569) * P(571) * P(577) * P(587) * P(593) * P(599) *
            P(601) * P(607) * P(613) * P(617) * P(619) * P(631) * P(641) *
            P(643) * P(647) * P(653) * P(659) * P(661) * P(673) * P(677) *
            P(683) * P(691) * P(701) * P(709) * P(719) * P(727) * P(733) *
            P(739) * P(743) * P(751) * P(757) * P(761) * P(769) * P(773) *
            P(787) * P(797) * P(809) * P(811) * P(821) * P(823) * P(827) *
            P(829);

    printf("The greatest common divisor of %d and %d is %d.\n", a, b, gcd);
    return 0;
}