Totient function: Difference between revisions
m
no edit summary
mNo edit summary |
|||
Line 293:
</pre>
=={{header|ALGOL-M}}==
The GCD approach is straight-forward and easy to follow, but is
<lang algol>
BEGIN
Line 2,885 ⟶ 2,883:
</pre>
=={{header|S-BASIC}}==
<lang basic>
$lines
rem - return p mod q
function mod(p, q = integer) = integer
end = p - q * (p / q)
rem - return greatest common divisor of x and y
function gcd(x, y = integer) = integer
var r, temp = integer
if x < y then
begin
temp = x
x = y
y = temp
end
r = mod(x, y)
while r <> 0 do
begin
x = y
y = r
r = mod(x, y)
end
end = y
rem - return phi (also called totient) of n
function phi(n = integer) = integer
var i, count = integer
count = 1
for i = 2 to n
if gcd(n, i) = 1 then count = count + 1
next i
end = count
rem - exercise the function
var n, totient, count = integer
print " n Phi(n) Prime?"
for n = 1 to 25
totient = phi(n)
print using "#### #### ";n, totient;
if totient + 1 = n then
print "yes"
else
print "no"
next n
rem - and further test it by counting primes
print
count = 0
for n = 1 to 1000
if phi(n) = n - 1 then count = count + 1
if n = 100 then
print "Primes up to 100 = ";count
else if n = 1000 then
print "Primes up to 1000 = ";count
next n
end
</lang>
{{out}}
<pre>
n Phi(n) Prime?
1 1 no
2 1 yes
3 2 yes
4 2 no
5 4 yes
6 2 no
7 6 yes
8 4 no
9 6 no
10 4 no
11 10 yes
12 4 no
13 12 yes
14 6 no
15 8 no
16 8 no
17 16 yes
18 6 no
19 18 yes
20 8 no
21 12 no
22 10 no
23 22 yes
24 8 no
25 20 no
Primes up to 100 = 25
Primes up to 1000 = 168
</pre>
=={{header|Scala}}==
| |||