Coprimes
p and q are coprimes if they have no common factors other than 1.
- Task
Given the input pairs: [21,15],[17,23],[36,12],[18,29],[60,15] display whether they are coprimes.
11l
<lang 11l>F coprime(a, b)
R gcd(a, b) == 1
print([(21, 15),
(17, 23), (36, 12), (18, 29), (60, 15)].filter((x, y) -> coprime(x, y)))</lang>
- Output:
[(17, 23), (18, 29)]
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
Action!
<lang Action!>INT FUNC Gcd(INT a,b)
INT tmp
IF a<b THEN tmp=a a=b b=tmp FI
WHILE b#0 DO tmp=a MOD b a=b b=tmp OD
RETURN (a)
PROC Test(INT a,b)
CHAR ARRAY s0="not ",s1="",s
IF Gcd(a,b)=1 THEN s=s1 ELSE s=s0 FI PrintF("%I and %I are %Scoprimes%E",a,b,s)
RETURN
PROC Main()
Test(21,15) Test(17,23) Test(36,12) Test(18,29) Test(60,15)
RETURN</lang>
- Output:
Screenshot from Atari 8-bit computer
21 and 15 are not coprimes 17 and 23 are coprimes 36 and 12 are not coprimes 18 and 29 are coprimes 60 and 15 are not coprimes
ALGOL 68
<lang algol68>BEGIN # test the coprime-ness of some number pairs #
# iterative Greatest Common Divisor routine, returns the gcd of m and n # PROC gcd = ( INT m, n )INT: BEGIN INT a := ABS m, b := ABS n; WHILE b /= 0 DO INT new a = b; b := a MOD b; a := new a OD; a END # gcd # ; # pairs numbers to test # [,]INT pq = ( ( 21, 15 ), ( 17, 23 ), ( 36, 12 ), ( 18, 29 ), ( 60, 15 ) ); INT p pos = 2 LWB pq; INT q pos = 2 UPB pq; # test the pairs # FOR i FROM LWB pq TO UPB pq DO IF gcd( pq[ i, p pos ], pq[ i, q pos ] ) = 1 THEN # have a coprime pair # print( ( whole( pq[ i, p pos ], 0 ), " ", whole( pq[ i, q pos ], 0 ), newline ) ) FI OD
END</lang>
- Output:
17 23 18 29
ALGOL W
<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
<lang apl>(⊢(/⍨)1=∨/¨) (21 15)(17 23)(36 12)(18 29)(60 15)</lang>
- 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:
<lang applescript>{{17, 23}, {18, 29}}</lang>
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}}
Arturo
<lang rebol>coprimes?: function [a b] -> 1 = gcd @[a b]
loop [[21 15] [17 23] [36 12] [18 29] [60 15]] 'pair [
print [pair\0 "and" pair\1 "ara" (coprimes? pair\0 pair\1)? -> "coprimes." -> "not coprimes."]
]</lang>
- Output:
21 and 15 ara not coprimes. 17 and 23 ara coprimes. 36 and 12 ara not coprimes. 18 and 29 ara coprimes. 60 and 15 ara not coprimes.
AWK
<lang 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
BCPL
<lang bcpl>get "libhdr"
let gcd(a,b) = b=0 -> a, gcd(b, a rem b) let coprime(a,b) = gcd(a,b) = 1
let start() be $( let ps = table 21, 17, 36, 18, 60
let qs = table 15, 23, 12, 29, 15 let n = 5 for i=0 to n-1 if coprime(ps!i, qs!i) do writef("%N %N*N", ps!i, qs!i)
$)</lang>
- Output:
17 23 18 29
BQN
<lang bqn>GCD ← {𝕨(|𝕊⍟(>⟜0)⊣)𝕩} SelectCoprimes ← (1=GCD´¨)⊸/
SelectCoprimes ⟨21‿15,17‿23,36‿12,18‿29,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>
F#
<lang fsharp> // 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) </lang>
- Output:
17 and 23 are coprime 18 and 29 are coprime
Factor
<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
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
<lang J>([#~1=+./"1) >21 15;17 23;36 12;18 29;60 15</lang>
- Output:
17 23 18 29
jq
Works with gojq, the Go implementation of jq <lang jq>
- Note that jq optimizes the recursive call of _gcd in the following:
def gcd(a;b):
def _gcd: if .[1] != 0 then [.[1], .[0] % .[1]] | _gcd else .[0] end; [a,b] | _gcd ;
- Input: an array
def coprime: gcd(.[0]; .[1]) == 1; </lang> The task <lang jq>"The following pairs of numbers are coprime:", ([[21,15],[17,23],[36,12],[18,29],[60,15]][]
| select(coprime))
</lang>
- Output:
The following pairs of numbers are coprime: [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
Mathematica/Wolfram Language
<lang Mathematica>CoprimeQ @@@ {{21, 15}, {17, 23}, {36, 12}, {18, 29}, {60, 15}}</lang>
- Output:
{False, True, False, True, False}
Nim
<lang Nim>import math
for (a, b) in [(21, 15), (17, 23), (36, 12), (18, 29), (60, 15)]:
echo a, " and ", b, " are ", if gcd(a, b) == 1: "coprimes." else: "not coprimes."</lang>
- Output:
21 and 15 are not coprimes. 17 and 23 are coprimes. 36 and 12 are not coprimes. 18 and 29 are coprimes. 60 and 15 are not coprimes.
Perl
<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)]
Quackery
gcd
is defined at Greatest common divisor#Quackery.
<lang Quackery> [ gcd 1 = ] is coprime ( n n --> b )
' [ [ 21 15 ] [ 17 23 ] [ 36 12 ] [ 18 29 ] [ 60 15 ] ]
witheach [ unpack 2dup swap echo say " and " echo say " are" coprime not if [ say " not" ] say " coprime." cr ]</lang>
- Output:
21 and 15 are not coprime. 17 and 23 are coprime. 36 and 12 are not coprime. 18 and 29 are coprime. 60 and 15 are not coprime.
R
<lang R>factors <- function(n) c(Filter(function(x) n %% x == 0, seq_len(n %/% 2)), n) isCoprime <- function(p, q) all(intersect(factors(p), factors(q)) == 1) output <- data.frame(p = c(21, 17, 36, 18, 60), q = c(15, 23, 12, 29, 15)) print(transform(output, "Coprime" = ifelse(mapply(isCoprime, p, q), "Yes", "No")))</lang>
- Output:
p q Coprime 1 21 15 No 2 17 23 Yes 3 36 12 No 4 18 29 Yes 5 60 15 No
Racket
There is a coprime? function in the math/number-theory library to show off (more useful if you're using typed racket).
<lang racket>#lang racket/base
- Rename only necessary so we can distinguish it
(require (rename-in math/number-theory [coprime? number-theory/coprime?]))
(define (gcd/coprime? . ns)
(= 1 (apply gcd ns)))
(module+ main
(define ((Coprimes name coprime?) test) (printf "~a: ~a -> ~a~%" name (cons 'coprime? test) (apply coprime? test))) (define tests '([21 15] [17 23] [36 12] [18 29] [60 15] [21 15 27] [17 23 46]))
(for-each (λ (n f) (for-each (Coprimes n f) tests)) (list "math/number-theory" "named gcd-based function" "anonymous gcd-based function") (list number-theory/coprime? gcd/coprime? (λ ns (= 1 (apply gcd ns))))))</lang>
- Output:
math/number-theory: (coprime? 21 15) -> #f math/number-theory: (coprime? 17 23) -> #t math/number-theory: (coprime? 36 12) -> #f math/number-theory: (coprime? 18 29) -> #t math/number-theory: (coprime? 60 15) -> #f math/number-theory: (coprime? 21 15 27) -> #f math/number-theory: (coprime? 17 23 46) -> #t named gcd-based function: (coprime? 21 15) -> #f named gcd-based function: (coprime? 17 23) -> #t named gcd-based function: (coprime? 36 12) -> #f named gcd-based function: (coprime? 18 29) -> #t named gcd-based function: (coprime? 60 15) -> #f named gcd-based function: (coprime? 21 15 27) -> #f named gcd-based function: (coprime? 17 23 46) -> #t anonymous gcd-based function: (coprime? 21 15) -> #f anonymous gcd-based function: (coprime? 17 23) -> #t anonymous gcd-based function: (coprime? 36 12) -> #f anonymous gcd-based function: (coprime? 18 29) -> #t anonymous gcd-based function: (coprime? 60 15) -> #f anonymous gcd-based function: (coprime? 21 15 27) -> #f anonymous gcd-based function: (coprime? 17 23 46) -> #t
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
next
see "Found " + row + " coprimes" + nl see "done..." + nl </lang>
- Output:
working... input: [21,15],[17,23],[36,12],[18,29],[60,15] Coprimes are: 17 23 18 29 Found 2 coprimes done...
Ruby
<lang ruby>pairs = [[21,15],[17,23],[36,12],[18,29],[60,15]] pairs.select{|p, q| p.gcd(q) == 1}.each{|pair| p pair} </lang>
- Output:
[17, 23] [18, 29]
Sidef
<lang ruby>var pairs = [[21,15],[17,23],[36,12],[18,29],[60,15]] say "The following pairs of numbers are coprime:" pairs.grep { .gcd == 1 }.each { .say }</lang>
- Output:
The following pairs of numbers are coprime: [17, 23] [18, 29]
Wren
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]
XPL0
<lang XPL0>func GCD(A, B); \Return greatest common divisor of A and B int A, B; [while A#B do
if A>B then A:= A-B else B:= B-A;
return A; ];
int Input, N, A, B; [Input:= [[21,15], [17,23], [36,12], [18,29], [60,15]]; for N:= 0 to 4 do
[A:= Input(N, 0); B:= Input(N, 1); if GCD(A, B) = 1 then [IntOut(0, A); ChOut(0, ^,); IntOut(0, B); CrLf(0)]; ];
]</lang>
- Output:
17,23 18,29