Coprimes: Difference between revisions
(→{{header|Haskell}}: Added a definition and example in Haskell) |
|||
(50 intermediate revisions by 29 users not shown) | |||
Line 2: | Line 2: | ||
;Task: |
;Task: |
||
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'''. |
||
<br>Let input: [21,15],[17,23],[36,12],[18,29],[60,15] |
|||
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}}== |
|||
<syntaxhighlight 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,'$'</syntaxhighlight> |
|||
{{out}} |
|||
<pre>17 23 |
|||
18 29</pre> |
|||
=={{header|8086 Assembly}}== |
|||
<syntaxhighlight 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</syntaxhighlight> |
|||
{{out}} |
|||
<pre>17 23 |
|||
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}}== |
|||
<syntaxhighlight 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</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
17 23 |
|||
18 29 |
|||
</pre> |
|||
=={{header|ALGOL W}}== |
|||
{{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; |
|||
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.</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
COPRIMES |
|||
17 23 |
|||
18 29 |
|||
</pre> |
|||
=={{header|APL}}== |
|||
{{works with|Dyalog APL}} |
|||
<syntaxhighlight lang="apl">(⊢(/⍨)1=∨/¨) (21 15)(17 23)(36 12)(18 29)(60 15)</syntaxhighlight> |
|||
{{out}} |
|||
<pre>┌─────┬─────┐ |
|||
│17 23│18 29│ |
|||
└─────┴─────┘</pre> |
|||
=={{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 26: | 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 109: | 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}}== |
|||
<syntaxhighlight 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."] |
|||
]</syntaxhighlight> |
|||
{{out}} |
|||
<pre>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.</pre> |
|||
=={{header|AWK}}== |
|||
<syntaxhighlight 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) |
|||
} |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
17 23 |
|||
18 29 |
|||
</pre> |
|||
=={{header|BASIC}}== |
|||
<syntaxhighlight 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</syntaxhighlight> |
|||
{{out}} |
|||
<pre> 17 23 |
|||
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}}== |
|||
<syntaxhighlight 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; |
|||
}</syntaxhighlight> |
|||
{{out}} |
|||
<pre>{17, 23} |
|||
{18, 29}</pre> |
|||
=={{header|C++}}== |
|||
<syntaxhighlight 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; |
|||
}</syntaxhighlight> |
|||
{{out}} |
|||
<pre>{17, 23} |
|||
{18, 29}</pre> |
|||
=={{header|Cowgol}}== |
|||
<syntaxhighlight 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;</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#}}== |
|||
<syntaxhighlight 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) |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
17 and 23 are coprime |
|||
18 and 29 are coprime |
|||
</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 127: | 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 136: | Line 686: | ||
{ 60 15 } |
{ 60 15 } |
||
{ 21 22 25 31 143 } Coprime |
{ 21 22 25 31 143 } Coprime |
||
</pre> |
|||
=={{header|Fermat}}== |
|||
<syntaxhighlight lang="fermat">Func Is_coprime(a, b) = if GCD(a,b)=1 then 1 else 0 fi.</syntaxhighlight> |
|||
=={{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.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</syntaxhighlight> |
|||
{{out}} |
|||
<pre>= 17= 23 |
|||
= 18= 29</pre> |
|||
=={{header|FreeBASIC}}== |
|||
<syntaxhighlight 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) |
|||
</syntaxhighlight> |
|||
{{out}}<pre> |
|||
false |
|||
true |
|||
false |
|||
true |
|||
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 141: | 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 156: | Line 778: | ||
} |
} |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 166: | Line 788: | ||
=={{header|Haskell}}== |
=={{header|Haskell}}== |
||
< |
<syntaxhighlight lang="haskell">------------------------- COPRIMES ----------------------- |
||
coprime :: Integral a => a -> a -> Bool |
coprime :: Integral a => a -> a -> Bool |
||
Line 183: | 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> |
||
=={{header|J}}== |
|||
<syntaxhighlight lang="j">([#~1=+./"1) >21 15;17 23;36 12;18 29;60 15</syntaxhighlight> |
|||
{{out}} |
|||
<pre>17 23 |
|||
18 29</pre> |
|||
=={{header|jq}}== |
|||
{{works with|jq}} |
|||
'''Works with gojq, the Go implementation of jq''' |
|||
<syntaxhighlight 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; |
|||
</syntaxhighlight> |
|||
'''The task''' |
|||
<syntaxhighlight lang="jq">"The following pairs of numbers are coprime:", |
|||
([[21,15],[17,23],[36,12],[18,29],[60,15]][] |
|||
| select(coprime)) |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
The following pairs of numbers are coprime: |
|||
[17,23] |
|||
[18,29] |
|||
</pre> |
|||
=={{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 196: | Line 849: | ||
[21, 22, 25, 31, 143] |
[21, 22, 25, 31, 143] |
||
</pre> |
</pre> |
||
=={{header|MAD}}== |
|||
<syntaxhighlight 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 </syntaxhighlight> |
|||
{{out}} |
|||
<pre>COPRIMES |
|||
17 23 |
|||
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}}== |
|||
<syntaxhighlight 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."</syntaxhighlight> |
|||
{{out}} |
|||
<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|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}}== |
|||
{{libheader|ntheory}} |
|||
<syntaxhighlight 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]; |
|||
</syntaxhighlight> |
|||
{{out}} |
|||
<pre> 21, 15 |
|||
Coprime 17, 23 |
|||
36, 12 |
|||
Coprime 18, 29 |
|||
60, 15 |
|||
Coprime 21, 22, 25, 31, 143</pre> |
|||
=={{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 207: | 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 217: | 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}}== |
|||
<syntaxhighlight 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</syntaxhighlight> |
|||
{{out}} |
|||
<pre>17 23 |
|||
18 29</pre> |
|||
=={{header|Python}}== |
=={{header|Python}}== |
||
< |
<syntaxhighlight lang="python">'''Coprimes''' |
||
from math import gcd |
from math import gcd |
||
Line 249: | 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> |
||
=={{header|Quackery}}== |
|||
<code>gcd</code> is defined at [[Greatest common divisor#Quackery]]. |
|||
<syntaxhighlight 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 ]</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|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 265: | 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 @ |
|||
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' |
||
do j=1 for words(@); say /*process |
do j=1 for words(@); say /*process each of the sets of numbers. */ |
||
stuff= translate( word(@, j), , ',') /*change |
stuff= translate( word(@, j), , ',') /*change commas (,) to blanks for GCD.*/ |
||
cofactor= gcd(stuff) /*get |
cofactor= gcd(stuff) /*get Greatest Common Divisor of #'s.*/ |
||
if cofactor==1 then say stuff " ─────── are coprime ───────" |
if cofactor==1 then say stuff " ─────── are coprime ───────" |
||
else say stuff " have a cofactor of: " cofactor |
else say stuff " have a cofactor of: " cofactor |
||
Line 277: | Line 1,187: | ||
exit 0 /*stick a fork in it, we're all done. */ |
exit 0 /*stick a fork in it, we're all done. */ |
||
/*──────────────────────────────────────────────────────────────────────────────────────*/ |
/*──────────────────────────────────────────────────────────────────────────────────────*/ |
||
gcd: procedure; |
gcd: procedure; parse arg $ /*╔═══════════════════════════════════╗*/ |
||
do #= |
do #=2 for arg()-1; $= $ arg(#) /*║This GCD handles multiple arguments║*/ |
||
end /*#*/ /*║ |
end /*#*/ /*║ & multiple numbers per argument, &║*/ |
||
parse var $ x z . /* |
parse var $ x z . /*║negative numbers and non-integers. ║*/ |
||
if x=0 then x= z; x= abs(x) /* |
if x=0 then x= z; x= abs(x) /*╚═══════════════════════════════════╝*/ |
||
do j=2 to words($); y= abs( word($, j) ); if y=0 then iterate |
do j=2 to words($); y= abs( word($, j) ); if y=0 then iterate |
||
do until _==0; _= x//y; x= y; y= _ |
do until _==0; _= x // y; x= y; y= _ |
||
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 307: | Line 1,217: | ||
=={{header|Ring}}== |
=={{header|Ring}}== |
||
< |
<syntaxhighlight lang="ring"> |
||
see "working..." + nl |
see "working..." + nl |
||
row = 0 |
row = 0 |
||
Line 319: | Line 1,229: | ||
flag = 1 |
flag = 1 |
||
if Coprimes[n][1] < Coprimes[n][2] |
if Coprimes[n][1] < Coprimes[n][2] |
||
min = Coprimes[n][1] |
|||
else |
else |
||
min = Coprimes[n][2] |
|||
ok |
ok |
||
for m = 2 to |
for m = 2 to min |
||
if Coprimes[n][1]%m = 0 and Coprimes[n][2]%m = 0 |
if Coprimes[n][1]%m = 0 and Coprimes[n][2]%m = 0 |
||
flag = 0 |
flag = 0 |
||
Line 337: | 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 347: | 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> |
|||
=={{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:" |
|||
pairs.grep { .gcd == 1 }.each { .say }</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
The following pairs of numbers are coprime: |
|||
[17, 23] |
|||
[18, 29] |
|||
</pre> |
</pre> |
||
Line 352: | 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 363: | Line 1,311: | ||
[17, 23] |
[17, 23] |
||
[18, 29] |
[18, 29] |
||
</pre> |
|||
=={{header|XPL0}}== |
|||
<syntaxhighlight 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)]; |
|||
]; |
|||
]</syntaxhighlight> |
|||
{{out}} |
|||
<pre> |
|||
17,23 |
|||
18,29 |
|||
</pre> |
</pre> |
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