0
\$\begingroup\$

Find the highest common factor of two(positive integer) input numbers (not greater than 5000) in the minimum number of iterations.

If you use a loop, it should increment a counter, starting at 0 for the first run. The counter should be the first statement in the loop. If you use more than one loop, they too should have a similar counter.

So

counter_1=0;
counter_2=0;
...
loop{
    counter_1=counter_1 + 1;
    ...
    code
    ...

    loop_nested{
        counter_2=counter_2 + 1;
        ...
        code
        ...
    }
}
total_count=counter_1 + counter_2 + ...

Test cases first-number second-number-->expected-output

450 425-->25

27 23-->1

1000 1001-->1

36 54-->18

2 4000-->2

4000 2500-->500

2000 4000-->2000

99 75-->3

584 978-->2

3726 4380-->6

The code with the lowest sum of all counters for all test cases wins. There is no restriction on program length. Of course, you can't use any standard functions. There is no restriction on the language that you use.

Also, please write the sum of counters that your code produces.

| improve this question | |
\$\endgroup\$
  • 2
    \$\begingroup\$ In array-oriented languages like APL, J or R, this could be done without writing any (overt) loops at all, even without using the built-in GCD function. \$\endgroup\$ – marinus Aug 4 '13 at 19:04
  • 1
    \$\begingroup\$ Heck, it can be done even in GolfScript without any explicit loops! \$\endgroup\$ – Volatility Aug 4 '13 at 20:42
5
\$\begingroup\$

C, no loops -> 0 iterations

#include <stdlib.h>
#include <stdio.h>

#define Q(n) (a % (n) == 0 && b % (n) == 0) ? (n) :
#define R(n) Q((n)+9) Q((n)+8) Q((n)+7) Q((n)+6) Q((n)+5) Q((n)+4) Q((n)+3) Q((n)+2) Q((n)+1) Q(n)
#define S(n) R((n)+90) R((n)+80) R((n)+70) R((n)+60) R((n)+50) R((n)+40) R((n)+30) R((n)+20) R((n)+10) R(n)
#define T(n) S((n)+900) S((n)+800) S((n)+700) S((n)+600) S((n)+500) S((n)+400) S((n)+300) S((n)+200) S((n)+100) S(n)
#define U(n) T((n)+4000) T((n)+3000) T((n)+2000) T((n)+1000) T(n)

int main (int argc, char *argv[]) {
  int a, b, gcd;
  if (argc <= 2) {
    fprintf(stderr, "Usage: %s <num1> <num2>\n", argv[0]);
    return 1;
  }

  a = atoi(argv[1]);
  if (a < 1 || a > 5000) {
    fprintf(stderr, "Input %d out of range!\n", a);
    return 1;
  }

  b = atoi(argv[2]);
  if (b < 1 || b > 5000) {
    fprintf(stderr, "Input %d out of range!\n", b);
    return 1;
  }

  gcd = U(1) 0;

  if (gcd) {
    printf("The greatest common divisor of %d and %d is %d.\n", a, b, gcd);
  } else {
    fprintf(stderr, "Unable to find gcd of %d and %d! Inputs out of range?\n", a, b);
  }
  return 0;
}

Given that you've specified an upper limit of 5000 on the input values, this challenge can be solved in any language without any (runtime) loops just by taking a trivial solution using a single trial-division loop and unrolling it 5000 times.

I've chosen to use C, since the C macro preprocessor allows the solution to be written in a compact manner. The macros will be expanded at compile time into a single huge nested ternary ?: expression.

(If you consider the compile time macro expansion to be a loop in disguise, feel free to run the code above through the C preprocessor and consider the expanded output — which is also a valid C program — to be my solution. I won't include the expanded version in this post, though, since it's huge.)

| improve this answer | |
\$\endgroup\$
6
\$\begingroup\$

Along similar lines to Ilmari's solution, but slightly shorter (comparing expanded versions):

#include <stdlib.h>
#include <stdio.h>

#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 < 1 || a > 5000 || b < 1 || b > 5000) return 1;

    // Force an order: a <= b
    if (a > 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) & -(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;
}
| improve this answer | |
\$\endgroup\$
3
\$\begingroup\$

Ruby

def gcd(a,b)
  ('x'*a+' '+'x'*b).gsub(/^(.*)\1* \1+$/,'\1').length
end

A completely different solution - no explicit loops either.

| improve this answer | |
\$\endgroup\$
2
\$\begingroup\$

Tcl, 0 loops.

Some languages don't even have loops, they use recursion.

Note: if you don't use Tcl 8.6, replace tailcall with return [...]

proc gcd {a b} {
    if {$b > $a} {tailcall gcd $b $a}
    if {$b == 0} {return $a}
    tailcall gcd $b [expr {$a % $b}]
}

Well, and here for the people that said recursion is a loop:

proc gcd2 {a b {i 0}} {
    if {$b > $a} {lassign [list $a $b] b a}
    if {$b == 0} {return $a}
    set a [expr {$a % $b}]
    if {$a == 0} {return $b}
    set b [expr {$b % $a}]
    if {$b == 0} {return $a}
    set a [expr {$a % $b}]
    if {$a == 0} {return $b}
    set b [expr {$b % $a}]
    if {$b == 0} {return $a}
    set a [expr {$a % $b}]
    if {$a == 0} {return $b}
    set b [expr {$b % $a}]
    if {$b == 0} {return $a}
    set a [expr {$a % $b}]
    if {$a == 0} {return $b}
    set b [expr {$b % $a}]
    if {$b == 0} {return $a}
    set a [expr {$a % $b}]
    if {$a == 0} {return $b}
    set b [expr {$b % $a}]
    if {$b == 0} {return $a}
    set a [expr {$a % $b}]
    if {$a == 0} {return $b}
    set b [expr {$b % $a}]
    if {$b == 0} {return $a}
    set a [expr {$a % $b}]
    if {$a == 0} {return $b}
    set b [expr {$b % $a}]
    if {$b == 0} {return $a}
    set a [expr {$a % $b}]
    if {$a == 0} {return $b}
    set b [expr {$b % $a}]
    if {$b == 0} {return $a}
    set a [expr {$a % $b}]
    if {$a == 0} {return $b}
    set b [expr {$b % $a}]
    if {$b == 0} {return $a}
}
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Tail reucrsion is a form of looping, really :) \$\endgroup\$ – marinus Aug 4 '13 at 23:23
  • 1
    \$\begingroup\$ Well, because of the upper limit of 5000, I could replace the tail recursion with the procedure itself. \$\endgroup\$ – Johannes Kuhn Aug 5 '13 at 8:04
1
\$\begingroup\$

APL (0 loops)

All right, after some people have posted even smarter ideas I might as well post this one, which I wrote to support my comment. It has no loops or recursion expressed in it. 

∇GCD;divs;gcd
  divs ← {A/⍨A=⌈A←⍵÷⍳⍵}
  gcd  ← {⊃A/⍨(A←divs⍺)∊divs⍵}
  ⎕ ← ⎕ gcd ⎕
∇

For people who are not familiar with reading APL, I'll give all explict looping constructs that I know of below:

  • :For ... :EndFor (for loop)
  • :While ... :EndWhile (while loop)
  • fn¨list (apply fn to each element in list)
  • fn⍣N (apply fn N times)
  • fn⍣condfn (apply fn, until (condfn( x, fn( x ) ) is true)
  • {...∇...}: recursion ({...} is a function, ∇ refers to the function it is used in)

Explanation of the program:

  • divs: (get divisors of a number, in descending order)
    • A/⍨A=⌈A: select from A those elements where A is equal to ceil(A)
    • A←⍵÷⍳⍵: ...where A is the right argument (⍵) divided (÷) by the numbers from 1 to ⍵ (⍳⍵)
  • gcd: (get the greatest common denominator of two numbers)
    • ⊃: get the first (thus, biggest, see above) element of:
    • A/⍨: the elements selected from A, where...
    • (A←divs⍺): A, which is the divisors of the left argument,
    • ...∊divs⍵: ...is a member of the divisors of the right argument.
  • ⎕ ← ⎕ gcd ⎕: output (⎕ ←) the GCD of input (⎕) and input (⎕).
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Hi marinus, some of the characters are rendering as the 'not found' square when I look at this on Safari (OS X) – is there any chance you could clarify? \$\endgroup\$ – Benjamin R Jun 17 '16 at 3:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.