Totient function: Difference between revisions
m
→{{header|Wren}}: Minor tidy
(easylang) |
m (→{{header|Wren}}: Minor tidy) |
||
| (3 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 3,453 ⟶ 3,457:
There are 1229 primes below 10000</pre>
Alternative, faster version - around 0.04 seconds using LuaJIT on TIO.RUN.
{{Trans|ALGOL 68|so using the totient algorithm from the second Go sample}}
<syntaxhighlight lang="lua">
do
function totient( n ) -- returns the number of integers k where 1 <= k <= n that are mutually prime to n
if n < 3 then return 1
elseif n == 3 then return 2
else
local result, v, i = n, n, 2
while i * i <= v do
if v % i == 0 then
while v % i == 0 do v = math.floor( v / i ) end
result = result - math.floor( result / i )
end
if i == 2 then
i = 1
end
i = i + 2
end
if v > 1 then result = result - math.floor( result / v ) end
return result
end
end
-- show the totient function values for the first 25 integers
io.write( " n phi(n) remarks\n" )
for n = 1,25 do
local tn = totient( n )
io.write( string.format( "%2d", n ), ": ", string.format( "%5d", tn )
, ( tn == n - 1 and tn ~= 0 and " n is prime" or "" )
, "\n"
)
end
-- use the totient function to count primes
local n100, n1000, n10000, n100000 = 0, 0, 0, 0
for n = 1,100000 do
if totient( n ) == n - 1 then
if n <= 100 then n100 = n100 + 1 end
if n <= 1000 then n1000 = n1000 + 1 end
if n <= 10000 then n10000 = n10000 + 1 end
if n <= 100000 then n100000 = n100000 + 1 end
end
end
io.write( "There are ", string.format( "%6d", n100 ), " primes below 100\n" )
io.write( "There are ", string.format( "%6d", n1000 ), " primes below 1 000\n" )
io.write( "There are ", string.format( "%6d", n10000 ), " primes below 10 000\n" )
io.write( "There are ", string.format( "%6d", n100000 ), " primes below 100 000\n" )
end
</syntaxhighlight>
{{out}}
<pre>
n phi(n) remarks
1: 1
2: 1 n is prime
3: 2 n is prime
4: 2
5: 4 n is prime
6: 2
7: 6 n is prime
8: 4
9: 6
10: 4
11: 10 n is prime
12: 4
13: 12 n is prime
14: 6
15: 8
16: 8
17: 16 n is prime
18: 6
19: 18 n is prime
20: 8
21: 12
22: 10
23: 22 n is prime
24: 8
25: 20
There are 25 primes below 100
There are 168 primes below 1 000
There are 1229 primes below 10 000
There are 9592 primes below 100 000
</pre>
=={{header|MAD}}==
Line 5,051 ⟶ 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,430 ⟶ 5,584:
{{trans|Go}}
{{libheader|Wren-fmt}}
<syntaxhighlight lang="
var totient = Fn.new { |n|
| |||