Coprimes: Difference between revisions
(Added Algol W) |
(add FreeBASIC) |
||
Line 439: | Line 439: | ||
{ 60 15 } |
{ 60 15 } |
||
{ 21 22 25 31 143 } Coprime |
{ 21 22 25 31 143 } Coprime |
||
</pre> |
|||
=={{header|FreeBASIC}}== |
|||
<lang freebasic>function gcdp( a as uinteger, b as uinteger ) as uinteger |
|||
'returns the gcd of two positive integers |
|||
if b = 0 then return a |
|||
return gcdp( b, a mod b ) |
|||
end function |
|||
function gcd(a as integer, b as integer) as uinteger |
|||
'wrapper for gcdp, allows for negatives |
|||
return gcdp( abs(a), abs(b) ) |
|||
end function |
|||
function is_coprime( a as integer, b as integer ) as boolean |
|||
return (gcd(a,b)=1) |
|||
end function |
|||
print is_coprime(21,15) |
|||
print is_coprime(17,23) |
|||
print is_coprime(36,12) |
|||
print is_coprime(18,29) |
|||
print is_coprime(60,15) |
|||
</lang> |
|||
{{out}}<pre> |
|||
false |
|||
true |
|||
false |
|||
true |
|||
false |
|||
</pre> |
</pre> |
||
Revision as of 07:13, 27 April 2021
- Task
p and q are coprimes if they have no common factors other than 1.
Let input: [21,15],[17,23],[36,12],[18,29],[60,15]
8080 Assembly
<lang 8080asm>puts: equ 9 org 100h lxi h,pairs load: mov b,m ; Load the current pair into (B,C) inx h mov c,m inx h xra a ; Load C into A and set flags ora c rz ; If zero, we've reached the end push b ; Keep the current pair call gcd ; Calculate GCD pop b ; Restore the pair dcr a ; If GCD = 1, then GCD-1 = 0 jnz load ; If not, then try the next pair push h ; Keep the pair and the pointer push b mov a,b ; Print the first item call pnum pop b mov a,c ; Then the second item call pnum lxi d,nl ; Then print a newline mvi c,puts call 5 pop h ; Restore the pointer jmp load ;;; Let A = GCD(A,B) using the subtraction algorithm ;;; (The 8080 does not have division in hardware) gcd: cmp b ; Compare A and B rz ; If A == B, stop jc gcdsw ; If A < B, then swap them gcdsub: sub b ; Otherwise, A = A - B jmp gcd gcdsw: mov c,a ; Swap A and B mov a,b mov b,c jmp gcdsub ;;; Print the decimal value of A pnum: lxi d,nbuf ; End of output buffer mvi c,10 ; Divisor pdgt: mvi b,-1 ; Quotient pdgdiv: inr b ; Division by trial subtraction sub c jnc pdgdiv adi '0'+10 ; ASCII digit dcx d ; Store in buffer stax d xra a ; Continue with quotient ora b jnz pdgt ; If not zero dcr c ; CP/M syscall to print a string is 9 jmp 5 ;;; Pairs to test pairs: db 21,15 ; 2 bytes per pair db 17,23 db 36,12 db 18,29 db 60,15 db 0,0 ; end marker db '***' ; Number output buffer nbuf: db ' $' nl: db 13,10,'$'</lang>
- Output:
17 23 18 29
8086 Assembly
<lang asm>puts: equ 9 ; MS-DOS syscall to print a string cpu 8086 org 100h section .text mov si,pairs load: lodsw ; Load pair into AH,AL test ax,ax ; Stop on reaching 0 jz .done mov cx,ax ; Keep a copy out of harm's way call gcd ; Calculate GCD dec al ; If GCD=1 then GCD-1=0 jnz load ; If that is not the case, try next pair mov al,cl ; Otherwise, print the fist item call pnum mov al,ch ; Then the second item call pnum mov dx,nl ; Then a newline call pstr jmp load ; Then try the next pair .done: ret ;;; AL = gcd(AH,AL) gcd: cmp al,ah ; Compare AL and AH je .done ; If AL == AH, stop jg .sub ; If AL > AH, AL -= AH xchg al,ah ; Otherwise, swap them first .sub: sub al,ah jmp gcd .done: ret ;;; Print the decimal value of AL pnum: mov bx,nbuf ; Pointer to output buffer .dgt: aam ; AH = AL/10, AL = AL mod 10 add al,'0' ; Add ASCII 0 to digit dec bx ; Store digit in buffer mov [bx],al mov al,ah ; Continue with rest of number test al,al ; If not zero jnz .dgt mov dx,bx pstr: mov ah,puts ; Print the buffer using MS-DOS int 21h ret section .data db '***' ; Number output buffer nbuf: db ' $' nl: db 13,10,'$' ; Newline pairs: db 21,15 db 17,23 db 36,12 db 18,29 db 60,15 dw 0</lang>
- Output:
17 23 18 29
ALGOL W
<lang algolw>BEGIN % check whether sme numbers are coPrime (their gcd is 1) or not %
LOGICAL PROCEDURE COPRM ( INTEGER VALUE X, Y ) ; GCD( X, Y ) = 1; INTEGER PROCEDURE GCD ( INTEGER VALUE A, B ) ; BEGIN INTEGER AA, BB; AA := A; BB := B; WHILE AA NOT = BB DO BEGIN IF AA > BB THEN AA := AA - BB; IF AA < BB THEN BB := BB - AA END WHILE_AA_NE_BB ; AA END GCD ; INTEGER ARRAY P, Q ( 0 :: 4 ); INTEGER POS; POS := 0; FOR I := 21, 17, 36, 18, 60 DO BEGIN P( POS ) := I; POS := POS + 1 END; POS := 0; FOR I := 15, 23, 12, 29, 15 DO BEGIN Q( POS ) := I; POS := POS + 1 END; WRITE( "COPRIMES" ); FOR I := 0 UNTIL 4 DO BEGIN INTEGER PP, QQ; PP := P( I ); QQ := Q( I ); IF COPRM( PP, QQ ) THEN WRITE( I_W := 4, S_W := 0, PP, QQ ) END FOR_I
END.</lang>
- Output:
COPRIMES 17 23 18 29
APL
<lang apl>(⊢(/⍨)1=∨/¨) (21 15)(17 23)(36 12)(18 29)(60 15)</lang>
- Output:
┌─────┬─────┐ │17 23│18 29│ └─────┴─────┘
AppleScript
<lang applescript>on hcf(a, b)
repeat until (b = 0) set x to a set a to b set b to x mod b end repeat if (a < 0) then return -a return a
end hcf
local input, coprimes, thisPair, p, q set input to {{21, 15}, {17, 23}, {36, 12}, {18, 29}, {60, 15}} set coprimes to {} repeat with thisPair in input
set {p, q} to thisPair if (hcf(p, q) is 1) then set end of coprimes to thisPair's contents
end repeat return coprimes</lang>
- Output:
<lang applescript>{{17, 23}, {18, 29}}</lang>
or, composing a definition and test from more general functions:
<lang applescript>------------------------- COPRIME ------------------------
-- coprime :: Int -> Int -> Bool on coprime(a, b)
1 = gcd(a, b)
end coprime
TEST -------------------------
on run
script test on |λ|(xy) set {x, y} to xy coprime(x, y) end |λ| end script filter(test, ¬ {[21, 15], [17, 23], [36, 12], [18, 29], [60, 15]})
end run
GENERIC ------------------------
-- abs :: Num -> Num on abs(x)
-- Absolute value. if 0 > x then -x else x end if
end abs
-- filter :: (a -> Bool) -> [a] -> [a]
on filter(p, xs)
tell mReturn(p) set lst to {} set lng to length of xs repeat with i from 1 to lng set v to item i of xs if |λ|(v, i, xs) then set end of lst to v end repeat lst end tell
end filter
-- gcd :: Int -> Int -> Int
on gcd(a, b)
set x to abs(a) set y to abs(b) repeat until y = 0 if x > y then set x to x - y else set y to y - x end if end repeat return x
end gcd
-- mReturn :: First-class m => (a -> b) -> m (a -> b)
on mReturn(f)
-- 2nd class handler function lifted into 1st class script wrapper. if script is class of f then f else script property |λ| : f end script end if
end mReturn</lang>
- Output:
{{17, 23}, {18, 29}}
BASIC
<lang basic>10 DEFINT A-Z 20 READ N 30 FOR I=1 TO N 40 READ P,Q 50 A=P 60 B=Q 70 IF B THEN C=A: A=B: B=C MOD B: GOTO 70 80 IF A=1 THEN PRINT P;Q 90 NEXT I 100 DATA 5 110 DATA 21,15 120 DATA 17,23 130 DATA 36,12 140 DATA 18,29 150 DATA 60,15</lang>
- Output:
17 23 18 29
C
<lang c>#include <stdio.h>
int gcd(int a, int b) {
int c; while (b) { c = a; a = b; b = c % b; } return a;
}
struct pair {
int x, y;
};
void printPair(struct pair const *p) {
printf("{%d, %d}\n", p->x, p->y);
}
int main() {
struct pair pairs[] = { {21,15}, {17,23}, {36,12}, {18,29}, {60,15} }; int i; for (i=0; i<5; i++) { if (gcd(pairs[i].x, pairs[i].y) == 1) printPair(&pairs[i]); } return 0;
}</lang>
- Output:
{17, 23} {18, 29}
C++
<lang cpp>#include <iostream>
- include <algorithm>
- include <vector>
- include <utility>
int gcd(int a, int b) {
int c; while (b) { c = a; a = b; b = c % b; } return a;
}
int main() {
using intpair = std::pair<int,int>; std::vector<intpair> pairs = { {21,15}, {17,23}, {36,12}, {18,29}, {60,15} }; pairs.erase( std::remove_if( pairs.begin(), pairs.end(), [](const intpair& x) { return gcd(x.first, x.second) != 1; } ), pairs.end() ); for (auto& x : pairs) { std::cout << "{" << x.first << ", " << x.second << "}" << std::endl; } return 0;
}</lang>
- Output:
{17, 23} {18, 29}
Cowgol
<lang cowgol>include "cowgol.coh";
sub gcd(a: uint8, b: uint8): (r: uint8) is
while b != 0 loop r := a; a := b; b := r % b; end loop; r := a;
end sub;
record Pair is
x: uint8; y: uint8;
end record;
sub printPair(p: [Pair]) is
print_i8(p.x); print_char(' '); print_i8(p.y); print_nl();
end sub;
var pairs: Pair[] := {
{21,15}, {17,23}, {36,12}, {18,29}, {60,15}
};
var i: @indexof pairs := 0; while i < @sizeof pairs loop
if gcd(pairs[i].x, pairs[i].y) == 1 then printPair(&pairs[i]); end if; i := i + 1;
end loop;</lang>
Factor
<lang factor>USING: io kernel math prettyprint sequences ;
- coprime? ( seq -- ? ) [ ] [ simple-gcd ] map-reduce 1 = ;
{
{ 21 15 } { 17 23 } { 36 12 } { 18 29 } { 60 15 } { 21 22 25 31 143 }
} [ dup pprint coprime? [ " Coprime" write ] when nl ] each</lang>
- Output:
{ 21 15 } { 17 23 } Coprime { 36 12 } { 18 29 } Coprime { 60 15 } { 21 22 25 31 143 } Coprime
FreeBASIC
<lang freebasic>function gcdp( a as uinteger, b as uinteger ) as uinteger
'returns the gcd of two positive integers if b = 0 then return a return gcdp( b, a mod b )
end function
function gcd(a as integer, b as integer) as uinteger
'wrapper for gcdp, allows for negatives return gcdp( abs(a), abs(b) )
end function
function is_coprime( a as integer, b as integer ) as boolean
return (gcd(a,b)=1)
end function
print is_coprime(21,15) print is_coprime(17,23) print is_coprime(36,12) print is_coprime(18,29) print is_coprime(60,15) </lang>
- Output:
false true false true false
FOCAL
<lang focal>01.10 S P(1)=21; S Q(1)=15 01.20 S P(2)=17; S Q(2)=23 01.30 S P(3)=36; S Q(3)=12 01.40 S P(4)=18; S Q(4)=29 01.50 S P(5)=60; S Q(5)=15 01.60 F N=1,5;D 3 01.70 Q
02.10 I (A-B)2.2,2.6,2.4 02.20 S B=B-A 02.30 G 2.1 02.40 S A=A-B 02.50 G 2.1 02.60 R
03.10 S A=P(N) 03.20 S B=Q(N) 03.30 D 2 03.40 I (A-1)3.6,3.5,3.6 03.50 T %4,P(N),Q(N),! 03.60 R</lang>
- Output:
= 17= 23 = 18= 29
Go
Uses the same observation as the Wren entry. <lang go>package main
import (
"fmt" "rcu"
)
func main() {
pairs := [][2]int{{21, 15}, {17, 23}, {36, 12}, {18, 29}, {60, 15}} fmt.Println("The following pairs of numbers are coprime:") for _, pair := range pairs { if rcu.Gcd(pair[0], pair[1]) == 1 { fmt.Println(pair) } }
}</lang>
- Output:
The following pairs of numbers are coprime: [17 23] [18 29]
Haskell
<lang haskell>------------------------- COPRIMES -----------------------
coprime :: Integral a => a -> a -> Bool coprime a b = 1 == gcd a b
TEST -------------------------
main :: IO () main =
print $ filter ((1 ==) . uncurry gcd) [ (21, 15), (17, 23), (36, 12), (18, 29), (60, 15) ]</lang>
- Output:
[(17,23),(18,29)]
J
<lang J>([#~1=+./"1) >21 15;17 23;36 12;18 29;60 15</lang>
- Output:
17 23 18 29
Julia
<lang julia>filter(p -> gcd(p...) == 1, [[21,15],[17,23],[36,12],[18,29],[60,15],[21,22,25,31,143]])
</lang>
- Output:
3-element Vector{Vector{Int64}}:
[17, 23] [18, 29] [21, 22, 25, 31, 143]
MAD
<lang MAD> NORMAL MODE IS INTEGER
INTERNAL FUNCTION COPRM.(X,Y) = GCD.(X,Y).E.1 INTERNAL FUNCTION(A,B) ENTRY TO GCD. AA=A BB=B
LOOP WHENEVER AA.E.BB, FUNCTION RETURN AA
WHENEVER AA.G.BB, AA = AA-BB WHENEVER AA.L.BB, BB = BB-AA TRANSFER TO LOOP END OF FUNCTION VECTOR VALUES P = 21, 17, 36, 18, 60 VECTOR VALUES Q = 15, 23, 12, 29, 15 PRINT COMMENT $ COPRIMES $ THROUGH SHOW, FOR I=0, 1, I.GE.5 PP=P(I) QQ=Q(I)
SHOW WHENEVER COPRM.(PP, QQ), PRINT FORMAT FMT, PP, QQ
VECTOR VALUES FMT = $I4,I4*$ END OF PROGRAM </lang>
- Output:
COPRIMES 17 23 18 29
Perl
<lang perl>use strict; use warnings; use ntheory 'gcd';
printf "%7s %s\n", (gcd(@$_) == 1 ? 'Coprime' : ), join ', ', @$_
for [21,15], [17,23], [36,12], [18,29], [60,15], [21,22,25,31,143];
</lang>
- Output:
21, 15 Coprime 17, 23 36, 12 Coprime 18, 29 60, 15 Coprime 21, 22, 25, 31, 143
Phix
function gcd1(sequence s) return gcd(s)=1 end function ?filter({{21,15},{17,23},{36,12},{18,29},{60,15}},gcd1)
- Output:
{{17,23},{18,29}}
A longer set/element such as {21,22,25,30,143} would also be shown as coprime, since it is, albeit not pairwise coprime - for the latter you would need something like:
function pairwise_coprime(sequence s) for i=1 to length(s)-1 do for j=i+1 to length(s) do if gcd(s[i],s[j])!=1 then return false end if end for end for return true end function ?filter({{21,15},{17,23},{36,12},{18,29},{60,15},{21, 22, 25, 31, 143}},pairwise_coprime)
Output is the same as the above, because this excludes the {21, 22, 25, 31, 143}, since both 22 and 143 are divisible by 11.
PL/M
<lang plm>100H: BDOS: PROCEDURE (FN, ARG);
DECLARE FN BYTE, ARG ADDRESS; GO TO 5;
END BDOS;
PRINT: PROCEDURE (STRING);
DECLARE STRING ADDRESS; CALL BDOS(9, STRING);
END PRINT;
PRINT$BYTE: PROCEDURE (N);
DECLARE S (5) BYTE INITIAL ('... $'); DECLARE P ADDRESS, (N, C BASED P) BYTE; P = .S(3);
DIGIT:
P = P - 1; C = N MOD 10 + '0'; N = N / 10; IF N > 0 THEN GO TO DIGIT; CALL PRINT(P);
END PRINT$BYTE;
PRINT$PAIR: PROCEDURE (P, Q);
DECLARE (P, Q) BYTE; CALL PRINT$BYTE(P); CALL PRINT$BYTE(Q); CALL PRINT(.(13,10,'$'));
END PRINT$PAIR;
GCD: PROCEDURE (A, B) BYTE;
DECLARE (A, B, C) BYTE; DO WHILE B <> 0; C = A; A = B; B = C MOD B; END; RETURN A;
END GCD;
DECLARE P (5) BYTE INITIAL (21, 17, 36, 18, 60); DECLARE Q (5) BYTE INITIAL (15, 23, 12, 29, 15); DECLARE I BYTE;
DO I = 0 TO LAST(P);
IF GCD(P(I), Q(I)) = 1 THEN CALL PRINT$PAIR(P(I), Q(I));
END; CALL BDOS(0,0); EOF</lang>
- Output:
17 23 18 29
Python
<lang python>Coprimes
from math import gcd
- coprime :: Int -> Int -> Bool
def coprime(a, b):
True if a and b are coprime. return 1 == gcd(a, b)
- ------------------------- TEST -------------------------
- main :: IO ()
def main():
List of pairs filtered for coprimes
print([ xy for xy in [ (21, 15), (17, 23), (36, 12), (18, 29), (60, 15) ] if coprime(*xy) ])
- MAIN ---
if __name__ == '__main__':
main()</lang>
- Output:
[(17, 23), (18, 29)]
Raku
How do you determine if numbers are co-prime? Check to see if the Greatest common divisor is equal to one. Since we're duplicating tasks willy-nilly, lift code from that task, (or in this case, just use the builtin).
<lang perl6>say .raku, ( [gcd] |$_ ) == 1 ?? ' Coprime' !! for [21,15],[17,23],[36,12],[18,29],[60,15],[21,22,25,31,143]</lang>
[21, 15] [17, 23] Coprime [36, 12] [18, 29] Coprime [60, 15] [21, 22, 25, 31, 143] Coprime
REXX
<lang rexx>/*REXX prgm tests number sequences (min. of two #'s, separated by a commas) if comprime.*/ parse arg @ /*obtain optional arguments from the CL*/ if @= | @=="," then @= '21,15 17,23 36,12 18,29 60,15 21,22,25,143 -2,0 0,-3'
do j=1 for words(@); say /*process each of the sets of numbers. */ stuff= translate( word(@, j), , ',') /*change commas (,) to blanks for GCD.*/ cofactor= gcd(stuff) /*get Greatest Common Divisor of #'s.*/ if cofactor==1 then say stuff " ─────── are coprime ───────" else say stuff " have a cofactor of: " cofactor end /*j*/
exit 0 /*stick a fork in it, we're all done. */ /*──────────────────────────────────────────────────────────────────────────────────────*/ gcd: procedure; parse arg $ /*╔═══════════════════════════════════╗*/
do #=2 for arg()-1; $= $ arg(#) /*║This GCD handles multiple arguments║*/ end /*#*/ /*║ & multiple numbers per argument, &║*/ parse var $ x z . /*║negative numbers and non-integers. ║*/ if x=0 then x= z; x= abs(x) /*╚═══════════════════════════════════╝*/ do j=2 to words($); y= abs( word($, j) ); if y=0 then iterate do until _==0; _= x // y; x= y; y= _ end /*until*/ end /*j*/ return x</lang>
- output when using the default inputs:
21,15 have a cofactor of: 3 17,23 ─────── are coprime ─────── 36,12 have a cofactor of: 12 18,29 ─────── are coprime ─────── 60,15 have a cofactor of: 15 21,22,25,143 ─────── are coprime ─────── -2,0 have a cofactor of: 2 0,-3 have a cofactor of: 3
Ring
<lang ring> see "working..." + nl row = 0 Coprimes = [[21,15],[17,23],[36,12],[18,29],[60,15]] input = "input: [21,15],[17,23],[36,12],[18,29],[60,15]" see input + nl see "Coprimes are:" + nl
lncpr = len(Coprimes) for n = 1 to lncpr
flag = 1 if Coprimes[n][1] < Coprimes[n][2] min = Coprimes[n][1] else min = Coprimes[n][2] ok for m = 2 to min if Coprimes[n][1]%m = 0 and Coprimes[n][2]%m = 0 flag = 0 exit ok next if flag = 1 row = row + 1 see "" + Coprimes[n][1] + " " + Coprimes[n][2] + nl ok
next
see "Found " + row + " coprimes" + nl see "done..." + nl </lang>
- Output:
working... input: [21,15],[17,23],[36,12],[18,29],[60,15] Coprimes are: 17 23 18 29 Found 2 coprimes done...
Wren
Two numbers are coprime if their GCD is 1. <lang ecmascript>import "/math" for Int
var pairs = [[21,15],[17,23],[36,12],[18,29],[60,15]] System.print("The following pairs of numbers are coprime:") for (pair in pairs) if (Int.gcd(pair[0], pair[1]) == 1) System.print(pair)</lang>
- Output:
The following pairs of numbers are coprime: [17, 23] [18, 29]