highest common factor-fewest iterations [closed]

Question

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.

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. — marinus, Aug 4 '13 at 19:04
Heck, it can be done even in GolfScript without any explicit loops! — Volatility, Aug 4 '13 at 20:42
Voting to close because without a clear definition of "standard function" or "loop" (does recursion count? period-n quines? etc.). — Redwolf Programs, Jan 15 at 18:35

Ilmari Karonen · Accepted Answer · 2013-08-04 21:15:32Z

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.)

Peter Taylor · Accepted Answer · 2013-08-04 22:21:03Z

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;
}

Community · Accepted Answer · 2020-06-17 09:04:33Z

3

Ruby

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

A completely different solution - no explicit loops either.

edited Jun 17 '20 at 9:04

Community♦

1

answered Aug 5 '13 at 4:53

Howard

23.3k2 gold badges39 silver badges81 bronze badges

Add a comment |

Johannes Kuhn · Accepted Answer · 2013-08-05 09:17:33Z

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}
}

Well, because of the upper limit of 5000, I could replace the tail recursion with the procedure itself. — Johannes Kuhn, Aug 5 '13 at 8:04

marinus · Accepted Answer · 2013-08-04 23:55:24Z

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 (⎕).

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? — Benjamin R, Jun 17 '16 at 3:19

Stack Exchange Network

current community

your communities

more stack exchange communities

highest common factor-fewest iterations [closed]

5 Answers 5

C, no loops -> 0 iterations

Ruby

Tcl, 0 loops.

APL (0 loops)

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

Hot Network Questions

highest common factor-fewest iterations [closed]

5 Answers 5

C, no loops -> 0 iterations

Ruby

Tcl, 0 loops.

APL (0 loops)

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

Related

Hot Network Questions