Totient function: Difference between revisions
m
→{{header|Wren}}: Minor tidy
(→{{header|Lua}}: Added alternative version) |
m (→{{header|Wren}}: Minor tidy) |
||
| (2 intermediate revisions by 2 users not shown) | |||
Line 664:
FOR n TO 25 DO
INT tn = totient( n );
print( ( whole( n, -2 ), ": ", whole( tn, -5
, IF tn = n - 1 AND tn /= 0 THEN " n is prime" ELSE "" FI, newline
)
)
OD;
# use the totient function to count primes #
Line 714 ⟶ 717:
There are 9592 primes below 100 000
</pre>
=={{header|ALGOL-M}}==
The GCD approach is straight-forward and easy to follow, but is not particularly efficient.
Line 5,133 ⟶ 5,137:
10000: 1229
100000: 9592</pre>
=={{header|SETL}}==
<syntaxhighlight lang="setl">program totient;
loop for n in [1..1000000] do
tot := totient(n);
if tot = n-1 then prime +:= 1; end if;
if n <= 25 then
print(lpad(str n, 2), " ",
lpad(str tot, 2), " ",
if tot = n-1 then "prime" else "" end if);
end if;
if n in [1000,10000,100000,1000000] then
print(lpad(str prime,8), "primes up to" + lpad(str n,8));
end if;
end loop;
proc totient(n);
tot := n;
i := 2;
loop while i*i <= n do
if n mod i = 0 then
loop while n mod i = 0 do
n div:= i;
end loop;
tot -:= tot div i;
end if;
if i=2 then i:=3;
else i+:=2;
end if;
end loop;
if n>1 then
tot -:= tot div n;
end if;
return tot;
end proc;
end program;</syntaxhighlight>
{{out}}
<pre> 1 1
2 1 prime
3 2 prime
4 2
5 4 prime
6 2
7 6 prime
8 4
9 6
10 4
11 10 prime
12 4
13 12 prime
14 6
15 8
16 8
17 16 prime
18 6
19 18 prime
20 8
21 12
22 10
23 22 prime
24 8
25 20
168 primes up to 1000
1229 primes up to 10000
9592 primes up to 100000
78498 primes up to 1000000</pre>
=={{header|Shale}}==
Line 5,512 ⟶ 5,584:
{{trans|Go}}
{{libheader|Wren-fmt}}
<syntaxhighlight lang="
var totient = Fn.new { |n|
| |||