I'm working on modernizing Rosetta Code's infrastructure. Starting with communications. Please accept this time-limited open invite to RC's Slack.. --Michael Mol (talk) 20:59, 30 May 2020 (UTC)

Coprimes

From Rosetta Code
Coprimes is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.
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[edit]

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,'$'
Output:
17 23
18 29

8086 Assembly[edit]

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
Output:
17 23
18 29

ALGOL W[edit]

Translation of: MAD
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.
Output:
COPRIMES
  17  23
  18  29

APL[edit]

Works with: Dyalog APL
(⊢(/⍨)1=∨/¨) (21 15)(17 23)(36 12)(18 29)(60 15)
Output:
┌─────┬─────┐
│17 23│18 29│
└─────┴─────┘

AppleScript[edit]

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
Output:
{{17, 23}, {18, 29}}


or, composing a definition and test from more general functions:

------------------------- 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
Output:
{{17, 23}, {18, 29}}

AWK[edit]

 
# 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)
}
 
Output:
17 23
18 29

BASIC[edit]

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
Output:
 17  23
 18  29

C[edit]

#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;
}
Output:
{17, 23}
{18, 29}

C++[edit]

#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;
}
Output:
{17, 23}
{18, 29}

Cowgol[edit]

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;

F#[edit]

 
// Coprimes. Nigel Galloway: May 4th., 2021
let rec fN g=function 0->g=1 |n->fN n (g%n)
[(21,15);(17,23);(36,12);(18,29);(60,15)] |> List.filter(fun(n,g)->fN n g)|>List.iter(fun(n,g)->printfn "%d and %d are coprime" n g)
 
Output:
17 and 23 are coprime
18 and 29 are coprime

Factor[edit]

Works with: Factor version 0.98
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
Output:
{ 21 15 }
{ 17 23 } Coprime
{ 36 12 }
{ 18 29 } Coprime
{ 60 15 }
{ 21 22 25 31 143 } Coprime

Fermat[edit]

Func Is_coprime(a, b) = if GCD(a,b)=1 then 1 else 0 fi.

FOCAL[edit]

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
Output:
=   17=   23
=   18=   29

FreeBASIC[edit]

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)
 
Output:

false true false true false

Go[edit]

Library: Go-rcu

Uses the same observation as the Wren entry.

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)
}
}
}
Output:
The following pairs of numbers are coprime:
[17 23]
[18 29]

Haskell[edit]

------------------------- 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)
]
Output:
[(17,23),(18,29)]


J[edit]

([#~1=+./"1) >21 15;17 23;36 12;18 29;60 15
Output:
17 23
18 29

Julia[edit]

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

3-element Vector{Vector{Int64}}:

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

MAD[edit]

            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
Output:
COPRIMES
  17  23
  18  29

Perl[edit]

Library: ntheory
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];
 
Output:
        21, 15
Coprime 17, 23
        36, 12
Coprime 18, 29
        60, 15
Coprime 21, 22, 25, 31, 143

Phix[edit]

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[edit]

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
Output:
17 23
18 29

Python[edit]

'''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()
Output:
[(17, 23), (18, 29)]

Raku[edit]

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

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

REXX[edit]

/*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
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[edit]

 
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
next
 
see "Found " + row + " coprimes" + nl
see "done..." + nl
 
Output:
working...
input: [21,15],[17,23],[36,12],[18,29],[60,15]
Coprimes are:
17 23
18 29
Found 2 coprimes
done...

Wren[edit]

Library: Wren-math

Two numbers are coprime if their GCD is 1.

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)
Output:
The following pairs of numbers are coprime:
[17, 23]
[18, 29]