Totient function: Difference between revisions
Add Miranda
Not a robot (talk | contribs) (add BASIC) |
Not a robot (talk | contribs) (Add Miranda) |
||
Line 3,534:
9592</pre>
=={{header|Miranda}}+=
<syntaxhighlight lang="miranda">main :: [sys_message]
main = [Stdout (lay (map showline [1..25])),
Stdout (lay (map countprimes (25:map (10^) [2..5])))]
countprimes :: num->[char]
countprimes n = "There are " ++ show amount ++ " primes up to " ++ show n
where amount = #filter prime [2..n]
showline :: num->[char]
showline n = "phi(" ++ show n ++ ") = " ++ show (totient n) ++ ", " ++ kind
where kind = "prime", if prime n
= "composite", otherwise
prime :: num->bool
prime n = totient n = n - 1
totient :: num->num
totient n = loop n n (2:[3, 5..])
where loop tot n (d:ds)
= tot, if n<=1
= tot - tot div n, if d*d > n
= loop tot n ds, if n mod d ~= 0
= loop (tot - tot div d) (remfac n d) ds, otherwise
remfac n d = n, if n mod d ~= 0
= remfac (n div d) d, otherwise</syntaxhighlight>
{{out}}
<pre>phi(1) = 1, composite
phi(2) = 1, prime
phi(3) = 2, prime
phi(4) = 2, composite
phi(5) = 4, prime
phi(6) = 2, composite
phi(7) = 6, prime
phi(8) = 4, composite
phi(9) = 6, composite
phi(10) = 4, composite
phi(11) = 10, prime
phi(12) = 4, composite
phi(13) = 12, prime
phi(14) = 6, composite
phi(15) = 8, composite
phi(16) = 8, composite
phi(17) = 16, prime
phi(18) = 6, composite
phi(19) = 18, prime
phi(20) = 8, composite
phi(21) = 12, composite
phi(22) = 10, composite
phi(23) = 22, prime
phi(24) = 8, composite
phi(25) = 20, composite
There are 9 primes up to 25
There are 25 primes up to 100
There are 168 primes up to 1000
There are 1229 primes up to 10000
There are 9592 primes up to 100000</pre>
=={{header|Modula-2}}==
<syntaxhighlight lang="modula2">MODULE TotientFunction;
| |||