Coprimes: Difference between revisions

Content added Content deleted

Inline

Revision as of 17:07, 29 April 2021

Task

p and q are coprimes if they have no common factors other than 1.
Let input: [21,15],[17,23],[36,12],[18,29],[60,15]

8080 Assembly

<lang 8080asm>puts: equ 9 org 100h lxi h,pairs load: mov b,m ; Load the current pair into (B,C) inx h mov c,m inx h xra a ; Load C into A and set flags ora c rz ; If zero, we've reached the end push b ; Keep the current pair call gcd ; Calculate GCD pop b ; Restore the pair dcr a ; If GCD = 1, then GCD-1 = 0 jnz load ; If not, then try the next pair push h ; Keep the pair and the pointer push b mov a,b ; Print the first item call pnum pop b mov a,c ; Then the second item call pnum lxi d,nl ; Then print a newline mvi c,puts call 5 pop h ; Restore the pointer jmp load ;;; Let A = GCD(A,B) using the subtraction algorithm ;;; (The 8080 does not have division in hardware) gcd: cmp b ; Compare A and B rz ; If A == B, stop jc gcdsw ; If A < B, then swap them gcdsub: sub b ; Otherwise, A = A - B jmp gcd gcdsw: mov c,a ; Swap A and B mov a,b mov b,c jmp gcdsub ;;; Print the decimal value of A pnum: lxi d,nbuf ; End of output buffer mvi c,10 ; Divisor pdgt: mvi b,-1 ; Quotient pdgdiv: inr b ; Division by trial subtraction sub c jnc pdgdiv adi '0'+10 ; ASCII digit dcx d ; Store in buffer stax d xra a ; Continue with quotient ora b jnz pdgt ; If not zero dcr c ; CP/M syscall to print a string is 9 jmp 5 ;;; Pairs to test pairs: db 21,15 ; 2 bytes per pair db 17,23 db 36,12 db 18,29 db 60,15 db 0,0 ; end marker db '***' ; Number output buffer nbuf: db ' $' nl: db 13,10,'$'</lang>

Output:

17 23
18 29

8086 Assembly

<lang asm>puts: equ 9 ; MS-DOS syscall to print a string cpu 8086 org 100h section .text mov si,pairs load: lodsw ; Load pair into AH,AL test ax,ax ; Stop on reaching 0 jz .done mov cx,ax ; Keep a copy out of harm's way call gcd ; Calculate GCD dec al ; If GCD=1 then GCD-1=0 jnz load ; If that is not the case, try next pair mov al,cl ; Otherwise, print the fist item call pnum mov al,ch ; Then the second item call pnum mov dx,nl ; Then a newline call pstr jmp load ; Then try the next pair .done: ret ;;; AL = gcd(AH,AL) gcd: cmp al,ah ; Compare AL and AH je .done ; If AL == AH, stop jg .sub ; If AL > AH, AL -= AH xchg al,ah ; Otherwise, swap them first .sub: sub al,ah jmp gcd .done: ret ;;; Print the decimal value of AL pnum: mov bx,nbuf ; Pointer to output buffer .dgt: aam ; AH = AL/10, AL = AL mod 10 add al,'0' ; Add ASCII 0 to digit dec bx ; Store digit in buffer mov [bx],al mov al,ah ; Continue with rest of number test al,al ; If not zero jnz .dgt mov dx,bx pstr: mov ah,puts ; Print the buffer using MS-DOS int 21h ret section .data db '***' ; Number output buffer nbuf: db ' $' nl: db 13,10,'$' ; Newline pairs: db 21,15 db 17,23 db 36,12 db 18,29 db 60,15 dw 0</lang>

Output:

17 23
18 29

ALGOL W

Translation of: MAD

<lang algolw>BEGIN % check whether sme numbers are coPrime (their gcd is 1) or not %

   LOGICAL PROCEDURE COPRM ( INTEGER VALUE X, Y ) ; GCD( X, Y ) = 1;
   INTEGER PROCEDURE GCD ( INTEGER VALUE A, B ) ;
   BEGIN
       INTEGER AA, BB;
       AA := A;
       BB := B;
       WHILE AA NOT = BB DO BEGIN
           IF AA > BB THEN AA := AA - BB;
           IF AA < BB THEN BB := BB - AA
       END WHILE_AA_NE_BB  ;
       AA
   END GCD ;
   INTEGER ARRAY P, Q ( 0 :: 4 );
   INTEGER POS;
   POS := 0; FOR I := 21, 17, 36, 18, 60 DO BEGIN P( POS ) := I; POS := POS + 1 END;
   POS := 0; FOR I := 15, 23, 12, 29, 15 DO BEGIN Q( POS ) := I; POS := POS + 1 END;
   WRITE( "COPRIMES" );
   FOR I := 0 UNTIL 4 DO BEGIN
       INTEGER PP, QQ;
       PP := P( I );
       QQ := Q( I );
       IF COPRM( PP, QQ ) THEN WRITE( I_W := 4, S_W := 0, PP, QQ )
   END FOR_I

END.</lang>

Output:

COPRIMES
  17  23
  18  29

APL

Works with: Dyalog APL

Output:

┌─────┬─────┐
│17 23│18 29│
└─────┴─────┘

AppleScript

<lang applescript>on hcf(a, b)

   repeat until (b = 0)
       set x to a
       set a to b
       set b to x mod b
   end repeat
   
   if (a < 0) then return -a
   return a

end hcf

local input, coprimes, thisPair, p, q set input to {{21, 15}, {17, 23}, {36, 12}, {18, 29}, {60, 15}} set coprimes to {} repeat with thisPair in input

   set {p, q} to thisPair
   if (hcf(p, q) is 1) then set end of coprimes to thisPair's contents

end repeat return coprimes</lang>

Output:

or, composing a definition and test from more general functions: <lang applescript>------------------------- COPRIME ------------------------

-- coprime :: Int -> Int -> Bool on coprime(a, b)

   1 = gcd(a, b)

end coprime

TEST -------------------------

on run

   script test
       on |λ|(xy)
           set {x, y} to xy
           
           coprime(x, y)
       end |λ|
   end script
   
   filter(test, ¬
       {[21, 15], [17, 23], [36, 12], [18, 29], [60, 15]})

end run

GENERIC ------------------------

-- abs :: Num -> Num on abs(x)

   -- Absolute value.
   if 0 > x then
       -x
   else
       x
   end if

end abs

-- filter :: (a -> Bool) -> [a] -> [a] on filter(p, xs)

   tell mReturn(p)
       set lst to {}
       set lng to length of xs
       repeat with i from 1 to lng
           set v to item i of xs
           if |λ|(v, i, xs) then set end of lst to v
       end repeat
       lst
   end tell

end filter

-- gcd :: Int -> Int -> Int on gcd(a, b)

   set x to abs(a)
   set y to abs(b)
   repeat until y = 0
       if x > y then
           set x to x - y
       else
           set y to y - x
       end if
   end repeat
   return x

end gcd

-- mReturn :: First-class m => (a -> b) -> m (a -> b) on mReturn(f)

   -- 2nd class handler function lifted into 1st class script wrapper. 
   if script is class of f then
       f
   else
       script
           property |λ| : f
       end script
   end if

end mReturn</lang>

Output:

{{17, 23}, {18, 29}}

AWK

syntax: GAWK -f COPRIMES.AWK

BEGIN {

   n = split("21,15;17,23;36,12;18,29;60,15",arr1,";")
   for (i=1; i<=n; i++) {
     split(arr1[i],arr2,",")
     a = arr2[1]
     b = arr2[2]
     if (gcd(a,b) == 1) {
       printf("%d %d\n",a,b)
     }
   }
   exit(0)

} function gcd(p,q) {

   return(q?gcd(q,(p%q)):p)

} </lang>

Output:

17 23
18 29

BASIC

<lang basic>10 DEFINT A-Z 20 READ N 30 FOR I=1 TO N 40 READ P,Q 50 A=P 60 B=Q 70 IF B THEN C=A: A=B: B=C MOD B: GOTO 70 80 IF A=1 THEN PRINT P;Q 90 NEXT I 100 DATA 5 110 DATA 21,15 120 DATA 17,23 130 DATA 36,12 140 DATA 18,29 150 DATA 60,15</lang>

Output:

 17  23
 18  29

C

<lang c>#include <stdio.h>

int gcd(int a, int b) {

   int c;
   while (b) {
       c = a;
       a = b;
       b = c % b;
   }
   return a;

}

struct pair {

   int x, y;

};

void printPair(struct pair const *p) {

   printf("{%d, %d}\n", p->x, p->y);

}

int main() {

   struct pair pairs[] = {
       {21,15}, {17,23}, {36,12}, {18,29}, {60,15}
   };
   
   int i;
   for (i=0; i<5; i++) {
       if (gcd(pairs[i].x, pairs[i].y) == 1)
           printPair(&pairs[i]);
   }
   return 0;

}</lang>

Output:

{17, 23}
{18, 29}

C++

<lang cpp>#include <iostream>

include <algorithm>
include <vector>
include <utility>

int gcd(int a, int b) {

   int c;
   while (b) {
       c = a;
       a = b;
       b = c % b;
   }
   return a;

}

int main() {

   using intpair = std::pair<int,int>;
   std::vector<intpair> pairs = {
       {21,15}, {17,23}, {36,12}, {18,29}, {60,15}
   };
   
   pairs.erase(
       std::remove_if(
           pairs.begin(),
           pairs.end(),
           [](const intpair& x) {
               return gcd(x.first, x.second) != 1;
           }
       ),
       pairs.end()
   );
   
   for (auto& x : pairs) {
       std::cout << "{" << x.first 
                 << ", " << x.second 
                 << "}" << std::endl;
   }
   
   return 0;

}</lang>

Output:

{17, 23}
{18, 29}

Cowgol

<lang cowgol>include "cowgol.coh";

sub gcd(a: uint8, b: uint8): (r: uint8) is

   while b != 0 loop
       r := a;
       a := b;
       b := r % b;
   end loop;
   r := a;

end sub;

record Pair is

   x: uint8;
   y: uint8;

end record;

sub printPair(p: [Pair]) is

   print_i8(p.x);
   print_char(' ');
   print_i8(p.y);
   print_nl();

end sub;

var pairs: Pair[] := {

   {21,15}, {17,23}, {36,12}, {18,29}, {60,15}

};

var i: @indexof pairs := 0; while i < @sizeof pairs loop

   if gcd(pairs[i].x, pairs[i].y) == 1 then
       printPair(&pairs[i]);
   end if;
   i := i + 1;

end loop;</lang>

Factor

Works with: Factor version 0.98

<lang factor>USING: io kernel math prettyprint sequences ;

coprime? ( seq -- ? ) [ ] [ simple-gcd ] map-reduce 1 = ;

{

   { 21 15 }
   { 17 23 }
   { 36 12 }
   { 18 29 }
   { 60 15 }
   { 21 22 25 31 143 }

} [ dup pprint coprime? [ " Coprime" write ] when nl ] each</lang>

Output:

{ 21 15 }
{ 17 23 } Coprime
{ 36 12 }
{ 18 29 } Coprime
{ 60 15 }
{ 21 22 25 31 143 } Coprime

Fermat

<lang fermat>Func Is_coprime(a, b) = if GCD(a,b)=1 then 1 else 0 fi.</lang>

FOCAL

<lang focal>01.10 S P(1)=21; S Q(1)=15 01.20 S P(2)=17; S Q(2)=23 01.30 S P(3)=36; S Q(3)=12 01.40 S P(4)=18; S Q(4)=29 01.50 S P(5)=60; S Q(5)=15 01.60 F N=1,5;D 3 01.70 Q

02.10 I (A-B)2.2,2.6,2.4 02.20 S B=B-A 02.30 G 2.1 02.40 S A=A-B 02.50 G 2.1 02.60 R

03.10 S A=P(N) 03.20 S B=Q(N) 03.30 D 2 03.40 I (A-1)3.6,3.5,3.6 03.50 T %4,P(N),Q(N),! 03.60 R</lang>

Output:

=   17=   23
=   18=   29

FreeBASIC

<lang freebasic>function gcdp( a as uinteger, b as uinteger ) as uinteger

   'returns the gcd of two positive integers
   if b = 0 then return a
   return gcdp( b, a mod b )

end function

function gcd(a as integer, b as integer) as uinteger

   'wrapper for gcdp, allows for negatives
   return gcdp( abs(a), abs(b) )

end function

function is_coprime( a as integer, b as integer ) as boolean

   return (gcd(a,b)=1)

end function

print is_coprime(21,15) print is_coprime(17,23) print is_coprime(36,12) print is_coprime(18,29) print is_coprime(60,15) </lang>

Output:

false true false true false

Go

Library: Go-rcu

Uses the same observation as the Wren entry. <lang go>package main

import (

   "fmt"
   "rcu"

)

func main() {

   pairs := [][2]int{{21, 15}, {17, 23}, {36, 12}, {18, 29}, {60, 15}}
   fmt.Println("The following pairs of numbers are coprime:")
   for _, pair := range pairs {
       if rcu.Gcd(pair[0], pair[1]) == 1 {
           fmt.Println(pair)
       }
   }

}</lang>

Output:

The following pairs of numbers are coprime:
[17 23]
[18 29]

Haskell

<lang haskell>------------------------- COPRIMES -----------------------

coprime :: Integral a => a -> a -> Bool coprime a b = 1 == gcd a b

TEST -------------------------

main :: IO () main =

 print $
   filter
     ((1 ==) . uncurry gcd)
     [ (21, 15),
       (17, 23),
       (36, 12),
       (18, 29),
       (60, 15)
     ]</lang>

Output:

[(17,23),(18,29)]

J

Output:

17 23
18 29

Julia

<lang julia>filter(p -> gcd(p...) == 1, [[21,15],[17,23],[36,12],[18,29],[60,15],[21,22,25,31,143]])

</lang>

Output:


3-element Vector{Vector{Int64}}:

[17, 23]
[18, 29]
[21, 22, 25, 31, 143]

MAD

<lang MAD> NORMAL MODE IS INTEGER

           INTERNAL FUNCTION COPRM.(X,Y) = GCD.(X,Y).E.1
           
           INTERNAL FUNCTION(A,B)
           ENTRY TO GCD.
           AA=A
           BB=B

LOOP WHENEVER AA.E.BB, FUNCTION RETURN AA

           WHENEVER AA.G.BB, AA = AA-BB
           WHENEVER AA.L.BB, BB = BB-AA
           TRANSFER TO LOOP
           END OF FUNCTION
                       
           VECTOR VALUES P = 21, 17, 36, 18, 60
           VECTOR VALUES Q = 15, 23, 12, 29, 15
           
           PRINT COMMENT $ COPRIMES $
                
           THROUGH SHOW, FOR I=0, 1, I.GE.5
           PP=P(I)
           QQ=Q(I)

SHOW WHENEVER COPRM.(PP, QQ), PRINT FORMAT FMT, PP, QQ

           VECTOR VALUES FMT = $I4,I4*$
           END OF PROGRAM </lang>

Output:

COPRIMES
  17  23
  18  29

Perl

Library: ntheory

<lang perl>use strict; use warnings; use ntheory 'gcd';

printf "%7s %s\n", (gcd(@$_) == 1 ? 'Coprime' : ), join ', ', @$_

    for [21,15], [17,23], [36,12], [18,29], [60,15], [21,22,25,31,143];

</lang>

Output:

        21, 15
Coprime 17, 23
        36, 12
Coprime 18, 29
        60, 15
Coprime 21, 22, 25, 31, 143

Phix

function gcd1(sequence s) return gcd(s)=1 end function
?filter({{21,15},{17,23},{36,12},{18,29},{60,15}},gcd1)

Output:

{{17,23},{18,29}}

A longer set/element such as {21,22,25,30,143} would also be shown as coprime, since it is, albeit not pairwise coprime - for the latter you would need something like:

function pairwise_coprime(sequence s)
    for i=1 to length(s)-1 do
        for j=i+1 to length(s) do
            if gcd(s[i],s[j])!=1 then return false end if
        end for
    end for
    return true
end function
?filter({{21,15},{17,23},{36,12},{18,29},{60,15},{21, 22, 25, 31, 143}},pairwise_coprime)

Output is the same as the above, because this excludes the {21, 22, 25, 31, 143}, since both 22 and 143 are divisible by 11.

PL/M

<lang plm>100H: BDOS: PROCEDURE (FN, ARG);

   DECLARE FN BYTE, ARG ADDRESS;
   GO TO 5;

END BDOS;

PRINT: PROCEDURE (STRING);

   DECLARE STRING ADDRESS;
   CALL BDOS(9, STRING);

END PRINT;

PRINT$BYTE: PROCEDURE (N);

   DECLARE S (5) BYTE INITIAL ('... $');
   DECLARE P ADDRESS, (N, C BASED P) BYTE;
   P = .S(3);

DIGIT:

   P = P - 1;
   C = N MOD 10 + '0';
   N = N / 10;
   IF N > 0 THEN GO TO DIGIT;
   CALL PRINT(P);

END PRINT$BYTE;

PRINT$PAIR: PROCEDURE (P, Q);

   DECLARE (P, Q) BYTE;
   CALL PRINT$BYTE(P);
   CALL PRINT$BYTE(Q);
   CALL PRINT(.(13,10,'$'));

END PRINT$PAIR;

GCD: PROCEDURE (A, B) BYTE;

   DECLARE (A, B, C) BYTE;
   DO WHILE B <> 0;
       C = A;
       A = B;
       B = C MOD B;
   END;
   RETURN A;

END GCD;

DECLARE P (5) BYTE INITIAL (21, 17, 36, 18, 60); DECLARE Q (5) BYTE INITIAL (15, 23, 12, 29, 15); DECLARE I BYTE;

DO I = 0 TO LAST(P);

   IF GCD(P(I), Q(I)) = 1 THEN
       CALL PRINT$PAIR(P(I), Q(I));

END; CALL BDOS(0,0); EOF</lang>

Output:

17 23
18 29

Python

<lang python>Coprimes

from math import gcd

coprime :: Int -> Int -> Bool

def coprime(a, b):

   True if a and b are coprime.
   
   return 1 == gcd(a, b)

------------------------- TEST -------------------------
main :: IO ()

def main():

   List of pairs filtered for coprimes

   print([
       xy for xy in [
           (21, 15), (17, 23), (36, 12),
           (18, 29), (60, 15)
       ]
       if coprime(*xy)
   ])

MAIN ---

if __name__ == '__main__':

   main()</lang>

Output:

[(17, 23), (18, 29)]

Raku

How do you determine if numbers are co-prime? Check to see if the Greatest common divisor is equal to one. Since we're duplicating tasks willy-nilly, lift code from that task, (or in this case, just use the builtin).

<lang perl6>say .raku, ( [gcd] |$_ ) == 1 ?? ' Coprime' !! for [21,15],[17,23],[36,12],[18,29],[60,15],[21,22,25,31,143]</lang>

[21, 15]
[17, 23] Coprime
[36, 12]
[18, 29] Coprime
[60, 15]
[21, 22, 25, 31, 143] Coprime

REXX

<lang rexx>/*REXX prgm tests number sequences (min. of two #'s, separated by a commas) if comprime.*/ parse arg @ /*obtain optional arguments from the CL*/ if @= | @=="," then @= '21,15 17,23 36,12 18,29 60,15 21,22,25,143 -2,0 0,-3'

      do j=1  for words(@);     say             /*process each of the sets of numbers. */
      stuff= translate( word(@, j), , ',')      /*change commas (,) to blanks for  GCD.*/
      cofactor= gcd(stuff)                      /*get  Greatest Common Divisor  of #'s.*/
      if cofactor==1  then say  stuff  " ─────── are coprime ───────"
                      else say  stuff  " have a cofactor of: "       cofactor
      end   /*j*/

exit 0 /*stick a fork in it, we're all done. */ /*──────────────────────────────────────────────────────────────────────────────────────*/ gcd: procedure; parse arg $ /*╔═══════════════════════════════════╗*/

         do #=2  for arg()-1;   $= $  arg(#)    /*║This GCD handles multiple arguments║*/
         end   /*#*/                            /*║ & multiple numbers per argument, &║*/
      parse var  $    x  z  .                   /*║negative numbers and non-integers. ║*/
      if x=0  then x= z;        x= abs(x)       /*╚═══════════════════════════════════╝*/
         do j=2  to words($);   y= abs( word($, j) );               if y=0  then iterate
            do  until _==0;     _= x // y;            x= y;         y= _
            end   /*until*/
         end      /*j*/
      return x</lang>

output when using the default inputs:

21,15  have a cofactor of:  3

17,23  ─────── are coprime ───────

36,12  have a cofactor of:  12

18,29  ─────── are coprime ───────

60,15  have a cofactor of:  15

21,22,25,143  ─────── are coprime ───────

-2,0  have a cofactor of:  2

0,-3  have a cofactor of:  3

Ring

<lang ring> see "working..." + nl row = 0 Coprimes = [[21,15],[17,23],[36,12],[18,29],[60,15]] input = "input: [21,15],[17,23],[36,12],[18,29],[60,15]" see input + nl see "Coprimes are:" + nl

lncpr = len(Coprimes) for n = 1 to lncpr

   flag = 1
   if Coprimes[n][1] < Coprimes[n][2]
      min = Coprimes[n][1]
   else
      min = Coprimes[n][2]
   ok
   for m = 2 to min
       if Coprimes[n][1]%m = 0 and Coprimes[n][2]%m = 0 
          flag = 0
          exit
       ok 
   next  
   if flag = 1
      row = row + 1
      see "" + Coprimes[n][1] + " " + Coprimes[n][2] + nl
   ok

Output:

working...
input: [21,15],[17,23],[36,12],[18,29],[60,15]
Coprimes are:
17 23
18 29
Found 2 coprimes
done...

Wren

Library: Wren-math

Two numbers are coprime if their GCD is 1. <lang ecmascript>import "/math" for Int

var pairs = [[21,15],[17,23],[36,12],[18,29],[60,15]] System.print("The following pairs of numbers are coprime:") for (pair in pairs) if (Int.gcd(pair[0], pair[1]) == 1) System.print(pair)</lang>

Output:

The following pairs of numbers are coprime:
[17, 23]
[18, 29]