Totient function: Difference between revisions
m
→{{header|Wren}}: Minor tidy
Not a robot (talk | contribs) (Add PL/M) |
m (→{{header|Wren}}: Minor tidy) |
||
| (9 intermediate revisions by 7 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 751 ⟶ 755:
BEGIN
INTEGER I, COUNT;
BEGIN
IF GCD(N,I) = 1 THEN COUNT := COUNT + 1;
Line 758 ⟶ 762:
PHI := COUNT;
END;
COMMENT - EXERCISE THE FUNCTION;
Line 765 ⟶ 768:
FOR N := 1 STEP 1 UNTIL 25 DO
BEGIN
END;
Line 777 ⟶ 780:
IF N = 100 THEN
WRITE("PRIMES UP TO 100 =", COUNT)
WRITE("PRIMES UP TO 1000 =", COUNT);
END;
Line 2,484 ⟶ 2,487:
Number of primes up to 90000 = 8713
Number of primes up to 100000 = 9592</pre>
=={{header|EasyLang}}==
{{trans|AWK}}
<syntaxhighlight lang="easylang">
func totient n .
tot = n
i = 2
while i <= sqrt n
if n mod i = 0
while n mod i = 0
n = n div i
.
tot -= tot div i
.
if i = 2
i = 1
.
i += 2
.
if n > 1
tot -= tot div n
.
return tot
.
numfmt 0 3
print " N Prim Phi"
for n = 1 to 25
tot = totient n
x$ = " "
if n - 1 = tot
x$ = " x "
.
print n & x$ & tot
.
print ""
for n = 1 to 100000
tot = totient n
if n - 1 = tot
cnt += 1
.
if n = 100 or n = 1000 or n = 10000 or n = 100000
print n & " - " & cnt & " primes"
.
.
</syntaxhighlight>
=={{header|Factor}}==
Line 2,701 ⟶ 2,750:
{{FormulaeEntry|page=https://formulae.org/?script=examples/Euler%27s_totient_function}}
'''Solution'''
[[File:Fōrmulæ - Totient function 01.png]]
'''Case 1'''
[[File:Fōrmulæ - Totient function 02.png]]
[[File:Fōrmulæ - Totient function 03.png]]
'''Case 2'''
[[File:Fōrmulæ - Totient function 04.png]]
[[File:Fōrmulæ - Totient function 05.png]]
=={{header|Forth}}==
Line 3,392 ⟶ 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 4,054 ⟶ 4,201:
=={{header|Phix}}==
{{trans|Go}}
As of 1.0.2 there is a builtin phi().
<!--<syntaxhighlight lang="phix">(phixonline)-->
<span style="color: #008080;">function</span> <span style="color: #000000;">totient</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">)</span>
Line 4,127 ⟶ 4,275:
Number of primes up to 100000 = 9592
</pre>
=={{header|PL/I}}==
{{trans|C}}
<syntaxhighlight lang="pli">totientFunction: procedure options(main);
totient: procedure(nn) returns(fixed);
declare (nn, n, i, tot) fixed;
n = nn;
tot = n;
do i=2 repeat(i+2) while(i*i <= n);
if mod(n,i) = 0 then do;
do while(mod(n,i) = 0);
n = n / i;
end;
tot = tot - tot / i;
end;
if i=2 then i=1;
end;
if n>1 then tot = tot - tot/n;
return(tot);
end totient;
showPrimeCount: procedure(n, primeCount);
declare (n, primeCount) fixed;
put skip edit('There are', primeCount, ' primes up to', n) (A,F(5),A,F(6));
end showPrimeCount;
declare (n, primeCount, tot) fixed;
do n = 1 to 25;
tot = totient(n);
put edit('phi(', n, ') = ', tot) (A,F(2),A,F(2));
if tot = n-1 then do;
put list('; prime');
primeCount = primeCount + 1;
end;
put skip;
end;
call showPrimeCount(25, primeCount);
do n = 26 to 10000;
if totient(n) = n-1 then primeCount = primeCount + 1;
if n=100 | n=1000 | n=10000 then
call showPrimeCount(n, primeCount);
end;
end totientFunction;</syntaxhighlight>
{{out}}
<pre>phi( 1) = 1
phi( 2) = 1 ; prime
phi( 3) = 2 ; prime
phi( 4) = 2
phi( 5) = 4 ; prime
phi( 6) = 2
phi( 7) = 6 ; prime
phi( 8) = 4
phi( 9) = 6
phi(10) = 4
phi(11) = 10 ; prime
phi(12) = 4
phi(13) = 12 ; prime
phi(14) = 6
phi(15) = 8
phi(16) = 8
phi(17) = 16 ; prime
phi(18) = 6
phi(19) = 18 ; prime
phi(20) = 8
phi(21) = 12
phi(22) = 10
phi(23) = 22 ; prime
phi(24) = 8
phi(25) = 20
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</pre>
=={{header|PL/M}}==
Line 4,337 ⟶ 4,560:
=={{header|Quackery}}==
<code>gcd</code> is defined at [[Greatest common divisor#Quackery]].
<syntaxhighlight lang="quackery "> [ 0 swap dup times
[ i over gcd
1 = rot + swap ]
Line 4,917 ⟶ 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,296 ⟶ 5,584:
{{trans|Go}}
{{libheader|Wren-fmt}}
<syntaxhighlight lang="
var totient = Fn.new { |n|
| |||