Coprimes: Difference between revisions
(Add Factor) |
m (→{{header|Phix}}: added pairwise coprimes version) |
||
Line 183: | Line 183: | ||
{{17,23},{18,29}} |
{{17,23},{18,29}} |
||
</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 |
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: |
||
<!--<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;">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;">j</span><span style="color: #0000FF;">=</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: #008080;">do</span> |
|||
<span style="color: #008080;">if</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;">i</span><span style="color: #0000FF;">],</span><span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">j</span><span style="color: #0000FF;">])!=</span><span style="color: #000000;">1</span> <span style="color: #008080;">then</span> <span style="color: #008080;">return</span> <span style="color: #004600;">false</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
<span style="color: #008080;">return</span> <span style="color: #004600;">true</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> |
|||
<!--</lang>--> |
|||
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|Raku}}== |
=={{header|Raku}}== |
Revision as of 07:48, 21 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]
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}}
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
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]
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]
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.
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 program tests pairs of numbers (separated by a comma) to see if they're comprime.*/ parse arg @ 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 all commas (,) to blanks for GCD.*/ cofactor= gcd(stuff) /*get GCD (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; $= /*╔═══════════════════════════════════════╗*/
do #=1 for arg(); $= $ arg(#) /*║ This GCD can handle multiple arguments║*/ end /*#*/ /*║ and multiple numbers per argument, and║*/ 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] test = Coprimes[n][1] else test = Coprimes[n][2] ok for m = 2 to test 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]