Coprimes: Difference between revisions
(21 intermediate revisions by 16 users not shown) | |||
Line 4: | Line 4: | ||
'''p''' and '''q''' are coprimes if they have no common factors other than '''1'''. |
'''p''' and '''q''' are coprimes if they have no common factors other than '''1'''. |
||
Given the input pairs: [21,15],[17,23],[36,12],[18,29],[60,15] display whether they are coprimes. |
|||
<br><br> |
<br><br> |
||
=={{header|11l}}== |
|||
{{trans|Python}} |
|||
<syntaxhighlight 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)))</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
[(17, 23), (18, 29)] |
|||
</pre> |
|||
=={{header|8080 Assembly}}== |
=={{header|8080 Assembly}}== |
||
< |
<syntaxhighlight lang="8080asm">puts: equ 9 |
||
org 100h |
org 100h |
||
lxi h,pairs |
lxi h,pairs |
||
Line 70: | Line 87: | ||
db '***' ; Number output buffer |
db '***' ; Number output buffer |
||
nbuf: db ' $' |
nbuf: db ' $' |
||
nl: db 13,10,'$'</ |
nl: db 13,10,'$'</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>17 23 |
<pre>17 23 |
||
Line 76: | Line 93: | ||
=={{header|8086 Assembly}}== |
=={{header|8086 Assembly}}== |
||
< |
<syntaxhighlight lang="asm">puts: equ 9 ; MS-DOS syscall to print a string |
||
cpu 8086 |
cpu 8086 |
||
org 100h |
org 100h |
||
Line 126: | Line 143: | ||
db 18,29 |
db 18,29 |
||
db 60,15 |
db 60,15 |
||
dw 0</ |
dw 0</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>17 23 |
<pre>17 23 |
||
18 29</pre> |
18 29</pre> |
||
=={{header|Action!}}== |
|||
<syntaxhighlight 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</syntaxhighlight> |
|||
{{out}} |
|||
[https://gitlab.com/amarok8bit/action-rosetta-code/-/raw/master/images/Coprimes.png Screenshot from Atari 8-bit computer] |
|||
<pre> |
|||
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 |
|||
</pre> |
|||
=={{header|ALGOL 68}}== |
=={{header|ALGOL 68}}== |
||
< |
<syntaxhighlight lang="algol68">BEGIN # test the coprime-ness of some number pairs # |
||
# iterative Greatest Common Divisor routine, returns the gcd of m and n # |
# iterative Greatest Common Divisor routine, returns the gcd of m and n # |
||
PROC gcd = ( INT m, n )INT: |
PROC gcd = ( INT m, n )INT: |
||
Line 154: | Line 214: | ||
FI |
FI |
||
OD |
OD |
||
END</ |
END</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 163: | Line 223: | ||
=={{header|ALGOL W}}== |
=={{header|ALGOL W}}== |
||
{{Trans|MAD}} |
{{Trans|MAD}} |
||
< |
<syntaxhighlight 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; |
LOGICAL PROCEDURE COPRM ( INTEGER VALUE X, Y ) ; GCD( X, Y ) = 1; |
||
INTEGER PROCEDURE GCD ( INTEGER VALUE A, B ) ; |
INTEGER PROCEDURE GCD ( INTEGER VALUE A, B ) ; |
||
Line 187: | Line 247: | ||
IF COPRM( PP, QQ ) THEN WRITE( I_W := 4, S_W := 0, PP, QQ ) |
IF COPRM( PP, QQ ) THEN WRITE( I_W := 4, S_W := 0, PP, QQ ) |
||
END FOR_I |
END FOR_I |
||
END.</ |
END.</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 197: | Line 257: | ||
=={{header|APL}}== |
=={{header|APL}}== |
||
{{works with|Dyalog APL}} |
{{works with|Dyalog APL}} |
||
< |
<syntaxhighlight lang="apl">(⊢(/⍨)1=∨/¨) (21 15)(17 23)(36 12)(18 29)(60 15)</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>┌─────┬─────┐ |
<pre>┌─────┬─────┐ |
||
Line 204: | Line 264: | ||
=={{header|AppleScript}}== |
=={{header|AppleScript}}== |
||
< |
<syntaxhighlight lang="applescript">on hcf(a, b) |
||
repeat until (b = 0) |
repeat until (b = 0) |
||
set x to a |
set x to a |
||
Line 222: | Line 282: | ||
if (hcf(p, q) is 1) then set end of coprimes to thisPair's contents |
if (hcf(p, q) is 1) then set end of coprimes to thisPair's contents |
||
end repeat |
end repeat |
||
return coprimes</ |
return coprimes</syntaxhighlight> |
||
{{output}} |
{{output}} |
||
< |
<syntaxhighlight lang="applescript">{{17, 23}, {18, 29}}</syntaxhighlight> |
||
or, composing a definition and test from more general functions: |
or, composing a definition and test from more general functions: |
||
< |
<syntaxhighlight lang="applescript">------------------------- COPRIME ------------------------ |
||
-- coprime :: Int -> Int -> Bool |
-- coprime :: Int -> Int -> Bool |
||
Line 305: | Line 365: | ||
end script |
end script |
||
end if |
end if |
||
end mReturn</ |
end mReturn</syntaxhighlight> |
||
{{Out}} |
{{Out}} |
||
<pre>{{17, 23}, {18, 29}}</pre> |
<pre>{{17, 23}, {18, 29}}</pre> |
||
=={{header|Arturo}}== |
=={{header|Arturo}}== |
||
< |
<syntaxhighlight lang="rebol">coprimes?: function [a b] -> 1 = gcd @[a b] |
||
loop [[21 15] [17 23] [36 12] [18 29] [60 15]] 'pair [ |
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."] |
print [pair\0 "and" pair\1 "ara" (coprimes? pair\0 pair\1)? -> "coprimes." -> "not coprimes."] |
||
]</ |
]</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 325: | Line 385: | ||
=={{header|AWK}}== |
=={{header|AWK}}== |
||
<syntaxhighlight lang="awk"> |
|||
<lang AWK> |
|||
# syntax: GAWK -f COPRIMES.AWK |
# syntax: GAWK -f COPRIMES.AWK |
||
BEGIN { |
BEGIN { |
||
Line 342: | Line 402: | ||
return(q?gcd(q,(p%q)):p) |
return(q?gcd(q,(p%q)):p) |
||
} |
} |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 350: | Line 410: | ||
=={{header|BASIC}}== |
=={{header|BASIC}}== |
||
< |
<syntaxhighlight lang="basic">10 DEFINT A-Z |
||
20 READ N |
20 READ N |
||
30 FOR I=1 TO N |
30 FOR I=1 TO N |
||
Line 364: | Line 424: | ||
130 DATA 36,12 |
130 DATA 36,12 |
||
140 DATA 18,29 |
140 DATA 18,29 |
||
150 DATA 60,15</ |
150 DATA 60,15</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> 17 23 |
<pre> 17 23 |
||
18 29</pre> |
18 29</pre> |
||
=={{header|BCPL}}== |
|||
<syntaxhighlight 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) |
|||
$)</syntaxhighlight> |
|||
{{out}} |
|||
<pre>17 23 |
|||
18 29</pre> |
|||
=={{header|BQN}}== |
|||
<syntaxhighlight lang="bqn">GCD ← {𝕨(|𝕊⍟(>⟜0)⊣)𝕩} |
|||
SelectCoprimes ← (1=GCD´¨)⊸/ |
|||
SelectCoprimes ⟨21‿15,17‿23,36‿12,18‿29,60‿15⟩</syntaxhighlight> |
|||
{{out}} |
|||
<pre>⟨ ⟨ 17 23 ⟩ ⟨ 18 29 ⟩ ⟩</pre> |
|||
=={{header|C}}== |
=={{header|C}}== |
||
< |
<syntaxhighlight lang="c">#include <stdio.h> |
||
int gcd(int a, int b) { |
int gcd(int a, int b) { |
||
Line 401: | Line 487: | ||
} |
} |
||
return 0; |
return 0; |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>{17, 23} |
<pre>{17, 23} |
||
Line 407: | Line 493: | ||
=={{header|C++}}== |
=={{header|C++}}== |
||
< |
<syntaxhighlight lang="cpp">#include <iostream> |
||
#include <algorithm> |
#include <algorithm> |
||
#include <vector> |
#include <vector> |
||
Line 446: | Line 532: | ||
return 0; |
return 0; |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>{17, 23} |
<pre>{17, 23} |
||
Line 452: | Line 538: | ||
=={{header|Cowgol}}== |
=={{header|Cowgol}}== |
||
< |
<syntaxhighlight lang="cowgol">include "cowgol.coh"; |
||
sub gcd(a: uint8, b: uint8): (r: uint8) is |
sub gcd(a: uint8, b: uint8): (r: uint8) is |
||
Line 485: | Line 571: | ||
end if; |
end if; |
||
i := i + 1; |
i := i + 1; |
||
end loop;</ |
end loop;</syntaxhighlight> |
||
=={{header|Delphi}}== |
|||
{{works with|Delphi|6.0}} |
|||
{{libheader|SysUtils,StdCtrls}} |
|||
<syntaxhighlight lang="Delphi"> |
|||
function GreatestCommonDivisor(A,B: integer): integer; |
|||
begin |
|||
if B = 0 then Result:=A |
|||
else Result:=GreatestCommonDivisor( B, A mod B); |
|||
end; |
|||
function IsCoprime(A,B: integer): boolean; |
|||
begin |
|||
Result:=GreatestCommonDivisor(A,B)=1; |
|||
end; |
|||
const TestNumbers: array [0..4] of TPoint = |
|||
((X:21;Y:15),(X:17;Y:23),(X:36;Y:12),(X:18;Y:29),(X:60;Y:15)); |
|||
procedure ShowCoprimes(Memo: TMemo); |
|||
var I: integer; |
|||
var S: string; |
|||
var TN: TPoint; |
|||
begin |
|||
for I:=0 to High(TestNumbers) do |
|||
begin |
|||
TN:=TestNumbers[I]; |
|||
S:=IntToStr(TN.X)+' '+IntToStr(TN.Y)+' is '; |
|||
if IsCoprime(TN.X,TN.Y) then S:=S+'coprime' |
|||
else S:=S+'not coprime'; |
|||
Memo.Lines.Add(S); |
|||
end; |
|||
end; |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
21 15 is not coprime |
|||
17 23 is coprime |
|||
36 12 is not coprime |
|||
18 29 is coprime |
|||
60 15 is not coprime |
|||
Elapsed Time: 5.729 ms. |
|||
</pre> |
|||
=={{header|EasyLang}}== |
|||
<syntaxhighlight> |
|||
func gcd a b . |
|||
while b <> 0 |
|||
h = b |
|||
b = a mod b |
|||
a = h |
|||
. |
|||
return a |
|||
. |
|||
proc test p[] . . |
|||
if gcd p[1] p[2] = 1 |
|||
print p[] |
|||
. |
|||
. |
|||
pairs[][] = [ [ 21 15 ] [ 17 23 ] [ 36 12 ] [ 18 29 ] [ 60 15 ] ] |
|||
for i to len pairs[][] |
|||
test pairs[i][] |
|||
. |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
[ 17 23 ] |
|||
[ 18 29 ] |
|||
</pre> |
|||
=={{header|F_Sharp|F#}}== |
=={{header|F_Sharp|F#}}== |
||
< |
<syntaxhighlight lang="fsharp"> |
||
// Coprimes. Nigel Galloway: May 4th., 2021 |
// Coprimes. Nigel Galloway: May 4th., 2021 |
||
let rec fN g=function 0->g=1 |n->fN n (g%n) |
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) |
[(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) |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 498: | Line 662: | ||
18 and 29 are coprime |
18 and 29 are coprime |
||
</pre> |
</pre> |
||
=={{header|Factor}}== |
=={{header|Factor}}== |
||
{{works with|Factor|0.98}} |
{{works with|Factor|0.98}} |
||
< |
<syntaxhighlight lang="factor">USING: io kernel math prettyprint sequences ; |
||
: coprime? ( seq -- ? ) [ ] [ simple-gcd ] map-reduce 1 = ; |
: coprime? ( seq -- ? ) [ ] [ simple-gcd ] map-reduce 1 = ; |
||
Line 512: | Line 677: | ||
{ 21 22 25 31 143 } |
{ 21 22 25 31 143 } |
||
} |
} |
||
[ dup pprint coprime? [ " Coprime" write ] when nl ] each</ |
[ dup pprint coprime? [ " Coprime" write ] when nl ] each</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 524: | Line 689: | ||
=={{header|Fermat}}== |
=={{header|Fermat}}== |
||
< |
<syntaxhighlight lang="fermat">Func Is_coprime(a, b) = if GCD(a,b)=1 then 1 else 0 fi.</syntaxhighlight> |
||
=={{header|FOCAL}}== |
=={{header|FOCAL}}== |
||
< |
<syntaxhighlight lang="focal">01.10 S P(1)=21; S Q(1)=15 |
||
01.20 S P(2)=17; S Q(2)=23 |
01.20 S P(2)=17; S Q(2)=23 |
||
01.30 S P(3)=36; S Q(3)=12 |
01.30 S P(3)=36; S Q(3)=12 |
||
Line 547: | Line 712: | ||
03.40 I (A-1)3.6,3.5,3.6 |
03.40 I (A-1)3.6,3.5,3.6 |
||
03.50 T %4,P(N),Q(N),! |
03.50 T %4,P(N),Q(N),! |
||
03.60 R</ |
03.60 R</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>= 17= 23 |
<pre>= 17= 23 |
||
Line 553: | Line 718: | ||
=={{header|FreeBASIC}}== |
=={{header|FreeBASIC}}== |
||
< |
<syntaxhighlight lang="freebasic">function gcdp( a as uinteger, b as uinteger ) as uinteger |
||
'returns the gcd of two positive integers |
'returns the gcd of two positive integers |
||
if b = 0 then return a |
if b = 0 then return a |
||
Line 573: | Line 738: | ||
print is_coprime(18,29) |
print is_coprime(18,29) |
||
print is_coprime(60,15) |
print is_coprime(60,15) |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}}<pre> |
{{out}}<pre> |
||
false |
false |
||
Line 580: | Line 745: | ||
true |
true |
||
false |
false |
||
</pre> |
|||
=={{header|Frink}}== |
|||
<syntaxhighlight lang="frink">pairs = [ [21,15],[17,23],[36,12],[18,29],[60,15] ] |
|||
for [a,b] = pairs |
|||
println["[$a, $b] are " + (gcd[a,b] == 1 ? "" : "not ") + "coprime"]</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
[21, 15] are not coprime |
|||
[17, 23] are coprime |
|||
[36, 12] are not coprime |
|||
[18, 29] are coprime |
|||
[60, 15] are not coprime |
|||
</pre> |
</pre> |
||
Line 585: | Line 763: | ||
{{libheader|Go-rcu}} |
{{libheader|Go-rcu}} |
||
Uses the same observation as the Wren entry. |
Uses the same observation as the Wren entry. |
||
< |
<syntaxhighlight lang="go">package main |
||
import ( |
import ( |
||
Line 600: | Line 778: | ||
} |
} |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 610: | Line 788: | ||
=={{header|Haskell}}== |
=={{header|Haskell}}== |
||
< |
<syntaxhighlight lang="haskell">------------------------- COPRIMES ----------------------- |
||
coprime :: Integral a => a -> a -> Bool |
coprime :: Integral a => a -> a -> Bool |
||
Line 627: | Line 805: | ||
(18, 29), |
(18, 29), |
||
(60, 15) |
(60, 15) |
||
]</ |
]</syntaxhighlight> |
||
{{Out}} |
{{Out}} |
||
<pre>[(17,23),(18,29)]</pre> |
<pre>[(17,23),(18,29)]</pre> |
||
Line 633: | Line 811: | ||
=={{header|J}}== |
=={{header|J}}== |
||
< |
<syntaxhighlight lang="j">([#~1=+./"1) >21 15;17 23;36 12;18 29;60 15</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>17 23 |
<pre>17 23 |
||
Line 641: | Line 819: | ||
{{works with|jq}} |
{{works with|jq}} |
||
'''Works with gojq, the Go implementation of jq''' |
'''Works with gojq, the Go implementation of jq''' |
||
<syntaxhighlight lang="jq"> |
|||
<lang jq> |
|||
# Note that jq optimizes the recursive call of _gcd in the following: |
# Note that jq optimizes the recursive call of _gcd in the following: |
||
def gcd(a;b): |
def gcd(a;b): |
||
Line 650: | Line 828: | ||
# Input: an array |
# Input: an array |
||
def coprime: gcd(.[0]; .[1]) == 1; |
def coprime: gcd(.[0]; .[1]) == 1; |
||
</syntaxhighlight> |
|||
</lang> |
|||
'''The task''' |
'''The task''' |
||
< |
<syntaxhighlight lang="jq">"The following pairs of numbers are coprime:", |
||
([[21,15],[17,23],[36,12],[18,29],[60,15]][] |
([[21,15],[17,23],[36,12],[18,29],[60,15]][] |
||
| select(coprime)) |
| select(coprime)) |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 664: | Line 842: | ||
=={{header|Julia}}== |
=={{header|Julia}}== |
||
< |
<syntaxhighlight lang="julia">filter(p -> gcd(p...) == 1, [[21,15],[17,23],[36,12],[18,29],[60,15],[21,22,25,31,143]]) |
||
</ |
</syntaxhighlight>{{out}}<pre> |
||
3-element Vector{Vector{Int64}}: |
3-element Vector{Vector{Int64}}: |
||
[17, 23] |
[17, 23] |
||
Line 673: | Line 851: | ||
=={{header|MAD}}== |
=={{header|MAD}}== |
||
< |
<syntaxhighlight lang="mad"> NORMAL MODE IS INTEGER |
||
INTERNAL FUNCTION COPRM.(X,Y) = GCD.(X,Y).E.1 |
INTERNAL FUNCTION COPRM.(X,Y) = GCD.(X,Y).E.1 |
||
Line 698: | Line 876: | ||
VECTOR VALUES FMT = $I4,I4*$ |
VECTOR VALUES FMT = $I4,I4*$ |
||
END OF PROGRAM </ |
END OF PROGRAM </syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>COPRIMES |
<pre>COPRIMES |
||
17 23 |
17 23 |
||
18 29</pre> |
18 29</pre> |
||
=={{header|Mathematica}}/{{header|Wolfram Language}}== |
|||
<syntaxhighlight lang="mathematica">CoprimeQ @@@ {{21, 15}, {17, 23}, {36, 12}, {18, 29}, {60, 15}}</syntaxhighlight> |
|||
{{out}} |
|||
<pre>{False, True, False, True, False}</pre> |
|||
=={{header|MATLAB}}== |
|||
<syntaxhighlight lang="matlab">disp(coprime([21, 17, 36, 18, 60], [15, 23, 12, 29, 15])); |
|||
function coprimes = coprime(a,b) |
|||
gcds = gcd(a,b) == 1; |
|||
coprimes(1,:) = a(gcds); |
|||
coprimes(2,:) = b(gcds); |
|||
end</syntaxhighlight> |
|||
{{out}} |
|||
<pre> 17 18 |
|||
23 29</pre> |
|||
=={{header|Maxima}}== |
|||
<syntaxhighlight lang="maxima"> |
|||
/* Taken the list of pairs and making a sublist of those pairs that are coprimes */ |
|||
pairs:[[21,15],[17,23],[36,12],[18,29],[60,15]]$ |
|||
sublist(pairs,lambda([x],apply('gcd,x)=1)); |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
[[17,23],[18,29]] |
|||
</pre> |
|||
=={{header|Nim}}== |
=={{header|Nim}}== |
||
< |
<syntaxhighlight lang="nim">import math |
||
for (a, b) in [(21, 15), (17, 23), (36, 12), (18, 29), (60, 15)]: |
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."</ |
echo a, " and ", b, " are ", if gcd(a, b) == 1: "coprimes." else: "not coprimes."</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 716: | Line 923: | ||
18 and 29 are coprimes. |
18 and 29 are coprimes. |
||
60 and 15 are not coprimes.</pre> |
60 and 15 are not coprimes.</pre> |
||
=={{header|OCaml}}== |
|||
<syntaxhighlight lang="ocaml">let rec is_coprime a = function |
|||
| 0 -> a = 1 |
|||
| b -> is_coprime b (a mod b) |
|||
let () = |
|||
let p (a, b) = |
|||
Printf.printf "%u and %u are%s coprime\n" a b (if is_coprime a b then "" else " not") |
|||
in |
|||
List.iter p [21, 15; 17, 23; 36, 12; 18, 29; 60, 15]</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
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 |
|||
</pre> |
|||
=={{header|Perl}}== |
=={{header|Perl}}== |
||
{{libheader|ntheory}} |
{{libheader|ntheory}} |
||
< |
<syntaxhighlight lang="perl">use strict; |
||
use warnings; |
use warnings; |
||
use ntheory 'gcd'; |
use ntheory 'gcd'; |
||
Line 725: | Line 951: | ||
printf "%7s %s\n", (gcd(@$_) == 1 ? 'Coprime' : ''), join ', ', @$_ |
printf "%7s %s\n", (gcd(@$_) == 1 ? 'Coprime' : ''), join ', ', @$_ |
||
for [21,15], [17,23], [36,12], [18,29], [60,15], [21,22,25,31,143]; |
for [21,15], [17,23], [36,12], [18,29], [60,15], [21,22,25,31,143]; |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> 21, 15 |
<pre> 21, 15 |
||
Line 735: | Line 961: | ||
=={{header|Phix}}== |
=={{header|Phix}}== |
||
<!--< |
<!--<syntaxhighlight lang="phix">(phixonline)--> |
||
<span style="color: #008080;">function</span> <span style="color: #000000;">gcd1</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">return</span> <span style="color: #7060A8;">gcd</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">)=</span><span style="color: #000000;">1</span> <span style="color: #008080;">end</span> <span style="color: #008080;">function</span> |
<span style="color: #008080;">function</span> <span style="color: #000000;">gcd1</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">return</span> <span style="color: #7060A8;">gcd</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">)=</span><span style="color: #000000;">1</span> <span style="color: #008080;">end</span> <span style="color: #008080;">function</span> |
||
<span style="color: #0000FF;">?</span><span style="color: #7060A8;">filter</span><span style="color: #0000FF;">({{</span><span style="color: #000000;">21</span><span style="color: #0000FF;">,</span><span style="color: #000000;">15</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">17</span><span style="color: #0000FF;">,</span><span style="color: #000000;">23</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">36</span><span style="color: #0000FF;">,</span><span style="color: #000000;">12</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">18</span><span style="color: #0000FF;">,</span><span style="color: #000000;">29</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">60</span><span style="color: #0000FF;">,</span><span style="color: #000000;">15</span><span style="color: #0000FF;">}},</span><span style="color: #000000;">gcd1</span><span style="color: #0000FF;">)</span> |
<span style="color: #0000FF;">?</span><span style="color: #7060A8;">filter</span><span style="color: #0000FF;">({{</span><span style="color: #000000;">21</span><span style="color: #0000FF;">,</span><span style="color: #000000;">15</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">17</span><span style="color: #0000FF;">,</span><span style="color: #000000;">23</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">36</span><span style="color: #0000FF;">,</span><span style="color: #000000;">12</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">18</span><span style="color: #0000FF;">,</span><span style="color: #000000;">29</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">60</span><span style="color: #0000FF;">,</span><span style="color: #000000;">15</span><span style="color: #0000FF;">}},</span><span style="color: #000000;">gcd1</span><span style="color: #0000FF;">)</span> |
||
<!--</ |
<!--</syntaxhighlight>--> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 744: | Line 970: | ||
</pre> |
</pre> |
||
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: |
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: |
||
<!--< |
<!--<syntaxhighlight lang="phix">--> |
||
<span style="color: #008080;">function</span> <span style="color: #000000;">pairwise_coprime</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">)</span> |
<span style="color: #008080;">function</span> <span style="color: #000000;">pairwise_coprime</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">)</span> |
||
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">)-</span><span style="color: #000000;">1</span> <span style="color: #008080;">do</span> |
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">)-</span><span style="color: #000000;">1</span> <span style="color: #008080;">do</span> |
||
Line 754: | Line 980: | ||
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span> |
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span> |
||
<span style="color: #0000FF;">?</span><span style="color: #7060A8;">filter</span><span style="color: #0000FF;">({{</span><span style="color: #000000;">21</span><span style="color: #0000FF;">,</span><span style="color: #000000;">15</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">17</span><span style="color: #0000FF;">,</span><span style="color: #000000;">23</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">36</span><span style="color: #0000FF;">,</span><span style="color: #000000;">12</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">18</span><span style="color: #0000FF;">,</span><span style="color: #000000;">29</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">60</span><span style="color: #0000FF;">,</span><span style="color: #000000;">15</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">21</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">22</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">25</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">31</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">143</span><span style="color: #0000FF;">}},</span><span style="color: #000000;">pairwise_coprime</span><span style="color: #0000FF;">)</span> |
<span style="color: #0000FF;">?</span><span style="color: #7060A8;">filter</span><span style="color: #0000FF;">({{</span><span style="color: #000000;">21</span><span style="color: #0000FF;">,</span><span style="color: #000000;">15</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">17</span><span style="color: #0000FF;">,</span><span style="color: #000000;">23</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">36</span><span style="color: #0000FF;">,</span><span style="color: #000000;">12</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">18</span><span style="color: #0000FF;">,</span><span style="color: #000000;">29</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">60</span><span style="color: #0000FF;">,</span><span style="color: #000000;">15</span><span style="color: #0000FF;">},{</span><span style="color: #000000;">21</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">22</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">25</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">31</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">143</span><span style="color: #0000FF;">}},</span><span style="color: #000000;">pairwise_coprime</span><span style="color: #0000FF;">)</span> |
||
<!--</ |
<!--</syntaxhighlight>--> |
||
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. |
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. |
||
=={{header|PL/M}}== |
=={{header|PL/M}}== |
||
< |
<syntaxhighlight lang="plm">100H: |
||
BDOS: PROCEDURE (FN, ARG); |
BDOS: PROCEDURE (FN, ARG); |
||
DECLARE FN BYTE, ARG ADDRESS; |
DECLARE FN BYTE, ARG ADDRESS; |
||
Line 807: | Line 1,033: | ||
END; |
END; |
||
CALL BDOS(0,0); |
CALL BDOS(0,0); |
||
EOF</ |
EOF</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>17 23 |
<pre>17 23 |
||
Line 813: | Line 1,039: | ||
=={{header|Python}}== |
=={{header|Python}}== |
||
< |
<syntaxhighlight lang="python">'''Coprimes''' |
||
from math import gcd |
from math import gcd |
||
Line 841: | Line 1,067: | ||
# MAIN --- |
# MAIN --- |
||
if __name__ == '__main__': |
if __name__ == '__main__': |
||
main()</ |
main()</syntaxhighlight> |
||
{{Out}} |
{{Out}} |
||
<pre>[(17, 23), (18, 29)]</pre> |
<pre>[(17, 23), (18, 29)]</pre> |
||
Line 850: | Line 1,076: | ||
<code>gcd</code> is defined at [[Greatest common divisor#Quackery]]. |
<code>gcd</code> is defined at [[Greatest common divisor#Quackery]]. |
||
< |
<syntaxhighlight lang="quackery"> [ gcd 1 = ] is coprime ( n n --> b ) |
||
' [ [ 21 15 ] |
' [ [ 21 15 ] |
||
Line 864: | Line 1,090: | ||
coprime not if |
coprime not if |
||
[ say " not" ] |
[ say " not" ] |
||
say " coprime." cr ]</ |
say " coprime." cr ]</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 874: | Line 1,100: | ||
60 and 15 are not coprime. |
60 and 15 are not coprime. |
||
</pre> |
</pre> |
||
=={{header|R}}== |
|||
<syntaxhighlight lang="rsplus">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")))</syntaxhighlight> |
|||
{{out}} |
|||
<pre> p q Coprime |
|||
1 21 15 No |
|||
2 17 23 Yes |
|||
3 36 12 No |
|||
4 18 29 Yes |
|||
5 60 15 No</pre> |
|||
=={{header|Racket}}== |
|||
There is a coprime? function in the math/number-theory library to show off (more useful if you're using typed racket). |
|||
<syntaxhighlight 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))))))</syntaxhighlight> |
|||
{{out}} |
|||
<pre>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</pre> |
|||
=={{header|Raku}}== |
=={{header|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 [[Greatest_common_divisor#Raku|that task]], (or in this case, just use the builtin). |
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 [[Greatest_common_divisor#Raku|that task]], (or in this case, just use the builtin). |
||
<lang |
<syntaxhighlight lang="raku" line>say .raku, ( [gcd] |$_ ) == 1 ?? ' Coprime' !! '' for [21,15],[17,23],[36,12],[18,29],[60,15],[21,22,25,31,143]</syntaxhighlight> |
||
<pre>[21, 15] |
<pre>[21, 15] |
||
[17, 23] Coprime |
[17, 23] Coprime |
||
Line 887: | Line 1,175: | ||
=={{header|REXX}}== |
=={{header|REXX}}== |
||
< |
<syntaxhighlight 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*/ |
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' |
if @='' | @=="," then @= '21,15 17,23 36,12 18,29 60,15 21,22,25,143 -2,0 0,-3' |
||
Line 908: | Line 1,196: | ||
end /*until*/ |
end /*until*/ |
||
end /*j*/ |
end /*j*/ |
||
return x</ |
return x</syntaxhighlight> |
||
{{out|output|text= when using the default inputs:}} |
{{out|output|text= when using the default inputs:}} |
||
<pre> |
<pre> |
||
Line 929: | Line 1,217: | ||
=={{header|Ring}}== |
=={{header|Ring}}== |
||
< |
<syntaxhighlight lang="ring"> |
||
see "working..." + nl |
see "working..." + nl |
||
row = 0 |
row = 0 |
||
Line 959: | Line 1,247: | ||
see "Found " + row + " coprimes" + nl |
see "Found " + row + " coprimes" + nl |
||
see "done..." + nl |
see "done..." + nl |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 969: | Line 1,257: | ||
Found 2 coprimes |
Found 2 coprimes |
||
done... |
done... |
||
</pre> |
|||
=={{header|RPL}}== |
|||
<code>GCD</code> is defined at [[Greatest common divisor#RPL|Greatest common divisor]] |
|||
{{works with|HP|28}} |
|||
≪ → pairs |
|||
≪ { } |
|||
1 pairs SIZE '''FOR''' j |
|||
pairs j GET |
|||
DUP LIST→ DROP |
|||
'''IF''' <span style="color:blue">GCD</span> 1 == '''THEN''' 1 →LIST + '''ELSE''' DROP '''END''' |
|||
'''NEXT''' |
|||
≫ '<span style="color:blue">→COPR</span>' STO |
|||
{{21 15} {17 23} {36 12} {18 29} {60 15}} <span style="color:blue">→COPR</span> |
|||
{{out}} |
|||
<pre> |
|||
1: { { 17 23 } { 18 29 } } |
|||
</pre> |
|||
=={{header|Ruby}}== |
|||
<syntaxhighlight 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} |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre>[17, 23] |
|||
[18, 29] |
|||
</pre> |
</pre> |
||
=={{header|Sidef}}== |
=={{header|Sidef}}== |
||
< |
<syntaxhighlight lang="ruby">var pairs = [[21,15],[17,23],[36,12],[18,29],[60,15]] |
||
say "The following pairs of numbers are coprime:" |
say "The following pairs of numbers are coprime:" |
||
pairs.grep { .gcd == 1 }.each { .say }</ |
pairs.grep { .gcd == 1 }.each { .say }</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 985: | Line 1,300: | ||
{{libheader|Wren-math}} |
{{libheader|Wren-math}} |
||
Two numbers are coprime if their GCD is 1. |
Two numbers are coprime if their GCD is 1. |
||
< |
<syntaxhighlight lang="wren">import "./math" for Int |
||
var pairs = [[21,15],[17,23],[36,12],[18,29],[60,15]] |
var pairs = [[21,15],[17,23],[36,12],[18,29],[60,15]] |
||
System.print("The following pairs of numbers are coprime:") |
System.print("The following pairs of numbers are coprime:") |
||
for (pair in pairs) if (Int.gcd(pair[0], pair[1]) == 1) System.print(pair)</ |
for (pair in pairs) if (Int.gcd(pair[0], pair[1]) == 1) System.print(pair)</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 999: | Line 1,314: | ||
=={{header|XPL0}}== |
=={{header|XPL0}}== |
||
< |
<syntaxhighlight lang="xpl0">func GCD(A, B); \Return greatest common divisor of A and B |
||
int A, B; |
int A, B; |
||
[while A#B do |
[while A#B do |
||
Line 1,014: | Line 1,329: | ||
[IntOut(0, A); ChOut(0, ^,); IntOut(0, B); CrLf(0)]; |
[IntOut(0, A); ChOut(0, ^,); IntOut(0, B); CrLf(0)]; |
||
]; |
]; |
||
]</ |
]</syntaxhighlight> |
||
{{out}} |
{{out}} |
Latest revision as of 22:19, 25 March 2024
- Task
p and q are coprimes if they have no common factors other than 1.
Given the input pairs: [21,15],[17,23],[36,12],[18,29],[60,15] display whether they are coprimes.
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)))
- Output:
[(17, 23), (18, 29)]
8080 Assembly
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
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
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
- 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
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
- Output:
17 23 18 29
ALGOL W
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
(⊢(/⍨)1=∨/¨) (21 15)(17 23)(36 12)(18 29)(60 15)
- Output:
┌─────┬─────┐ │17 23│18 29│ └─────┴─────┘
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
- 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}}
Arturo
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."]
]
- 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
# 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
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
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)
$)
- Output:
17 23 18 29
BQN
GCD ← {𝕨(|𝕊⍟(>⟜0)⊣)𝕩}
SelectCoprimes ← (1=GCD´¨)⊸/
SelectCoprimes ⟨21‿15,17‿23,36‿12,18‿29,60‿15⟩
- Output:
⟨ ⟨ 17 23 ⟩ ⟨ 18 29 ⟩ ⟩
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;
}
- Output:
{17, 23} {18, 29}
C++
#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
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;
Delphi
function GreatestCommonDivisor(A,B: integer): integer;
begin
if B = 0 then Result:=A
else Result:=GreatestCommonDivisor( B, A mod B);
end;
function IsCoprime(A,B: integer): boolean;
begin
Result:=GreatestCommonDivisor(A,B)=1;
end;
const TestNumbers: array [0..4] of TPoint =
((X:21;Y:15),(X:17;Y:23),(X:36;Y:12),(X:18;Y:29),(X:60;Y:15));
procedure ShowCoprimes(Memo: TMemo);
var I: integer;
var S: string;
var TN: TPoint;
begin
for I:=0 to High(TestNumbers) do
begin
TN:=TestNumbers[I];
S:=IntToStr(TN.X)+' '+IntToStr(TN.Y)+' is ';
if IsCoprime(TN.X,TN.Y) then S:=S+'coprime'
else S:=S+'not coprime';
Memo.Lines.Add(S);
end;
end;
- Output:
21 15 is not coprime 17 23 is coprime 36 12 is not coprime 18 29 is coprime 60 15 is not coprime Elapsed Time: 5.729 ms.
EasyLang
func gcd a b .
while b <> 0
h = b
b = a mod b
a = h
.
return a
.
proc test p[] . .
if gcd p[1] p[2] = 1
print p[]
.
.
pairs[][] = [ [ 21 15 ] [ 17 23 ] [ 36 12 ] [ 18 29 ] [ 60 15 ] ]
for i to len pairs[][]
test pairs[i][]
.
- Output:
[ 17 23 ] [ 18 29 ]
F#
// 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
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
Func Is_coprime(a, b) = if GCD(a,b)=1 then 1 else 0 fi.
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
- Output:
= 17= 23 = 18= 29
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)
- Output:
false true false true false
Frink
pairs = [ [21,15],[17,23],[36,12],[18,29],[60,15] ]
for [a,b] = pairs
println["[$a, $b] are " + (gcd[a,b] == 1 ? "" : "not ") + "coprime"]
- Output:
[21, 15] are not coprime [17, 23] are coprime [36, 12] are not coprime [18, 29] are coprime [60, 15] are not coprime
Go
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
------------------------- 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
([#~1=+./"1) >21 15;17 23;36 12;18 29;60 15
- Output:
17 23 18 29
jq
Works with gojq, the Go implementation of 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;
The task
"The following pairs of numbers are coprime:",
([[21,15],[17,23],[36,12],[18,29],[60,15]][]
| select(coprime))
- Output:
The following pairs of numbers are coprime: [17,23] [18,29]
Julia
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
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
Mathematica/Wolfram Language
CoprimeQ @@@ {{21, 15}, {17, 23}, {36, 12}, {18, 29}, {60, 15}}
- Output:
{False, True, False, True, False}
MATLAB
disp(coprime([21, 17, 36, 18, 60], [15, 23, 12, 29, 15]));
function coprimes = coprime(a,b)
gcds = gcd(a,b) == 1;
coprimes(1,:) = a(gcds);
coprimes(2,:) = b(gcds);
end
- Output:
17 18 23 29
Maxima
/* Taken the list of pairs and making a sublist of those pairs that are coprimes */
pairs:[[21,15],[17,23],[36,12],[18,29],[60,15]]$
sublist(pairs,lambda([x],apply('gcd,x)=1));
- Output:
[[17,23],[18,29]]
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."
- 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.
OCaml
let rec is_coprime a = function
| 0 -> a = 1
| b -> is_coprime b (a mod b)
let () =
let p (a, b) =
Printf.printf "%u and %u are%s coprime\n" a b (if is_coprime a b then "" else " not")
in
List.iter p [21, 15; 17, 23; 36, 12; 18, 29; 60, 15]
- 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
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];
- 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
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
'''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)]
Quackery
gcd
is defined at Greatest common divisor#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 ]
- 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
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")))
- 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/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))))))
- 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).
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
/*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
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...
RPL
GCD
is defined at Greatest common divisor
≪ → pairs ≪ { } 1 pairs SIZE FOR j pairs j GET DUP LIST→ DROP IF GCD 1 == THEN 1 →LIST + ELSE DROP END NEXT ≫ '→COPR' STO
{{21 15} {17 23} {36 12} {18 29} {60 15}} →COPR
- Output:
1: { { 17 23 } { 18 29 } }
Ruby
pairs = [[21,15],[17,23],[36,12],[18,29],[60,15]]
pairs.select{|p, q| p.gcd(q) == 1}.each{|pair| p pair}
- Output:
[17, 23] [18, 29]
Sidef
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 }
- Output:
The following pairs of numbers are coprime: [17, 23] [18, 29]
Wren
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]
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)];
];
]
- Output:
17,23 18,29
- Draft Programming Tasks
- Prime Numbers
- 11l
- 8080 Assembly
- 8086 Assembly
- Action!
- ALGOL 68
- ALGOL W
- APL
- AppleScript
- Arturo
- AWK
- BASIC
- BCPL
- BQN
- C
- C++
- Cowgol
- Delphi
- SysUtils,StdCtrls
- EasyLang
- F Sharp
- Factor
- Fermat
- FOCAL
- FreeBASIC
- Frink
- Go
- Go-rcu
- Haskell
- J
- Jq
- Julia
- MAD
- Mathematica
- Wolfram Language
- MATLAB
- Maxima
- Nim
- OCaml
- Perl
- Ntheory
- Phix
- PL/M
- Python
- Quackery
- R
- Racket
- Raku
- REXX
- Ring
- RPL
- Ruby
- Sidef
- Wren
- Wren-math
- XPL0