Totient function: Difference between revisions
m
→{{header|Wren}}: Minor tidy
Not a robot (talk | contribs) (Add CLU) |
m (→{{header|Wren}}: Minor tidy) |
||
| (17 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 1,475 ⟶ 1,478:
1000000 78498
</pre>
=={{header|BASIC}}==
<syntaxhighlight lang="gwbasic">10 DEFINT A-Z: DIM B$(2): B$(0)="No": B$(1)="Yes"
20 PRINT " N Totient Prime"
30 FOR N=1 TO 25
40 GOSUB 200
50 P=-(T=N-1)
60 C=C+P
70 PRINT USING "## ####### \ \";N;T;B$(P)
80 NEXT N
90 F$="Number of primes up to ######: ####"
100 PRINT USING F$;25;C
110 FOR N=26 TO 10000
120 GOSUB 200
130 C=C-(T=N-1)
140 IF N=100 OR N=1000 OR N=10000 THEN PRINT USING F$;N;C
150 NEXT N
160 END
200 REM T = TOTIENT(N)
210 T=N: Z=N
220 I=2: GOSUB 270
230 I=3
240 IF I*I<=Z THEN GOSUB 270: I=I+2: GOTO 240
250 IF Z>1 THEN T=T-T\Z
260 RETURN
270 IF Z MOD I<>0 THEN RETURN
280 IF Z MOD I=0 THEN Z = Z\I: GOTO 280
290 T = T-T\I
300 RETURN</syntaxhighlight>
{{out}}
<pre> N Totient 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
Number of primes up to 25: 9
Number of primes up to 100: 25
Number of primes up to 1000: 168
Number of primes up to 10000: 1229</pre>
=={{header|BCPL}}==
{{trans|C}}
<syntaxhighlight lang="bcpl">get "libhdr"
let totient(n) = valof
$( let tot = n and i = 2
while i*i <= n
$( if n rem i = 0
$( while n rem i = 0 do n := n / i
tot := tot - tot/i
$)
if i=2 then i:=1
i := i+2
$)
resultis n>1 -> tot-tot/n, tot
$)
let start() be
$( let count = 0
writes(" N Totient Prime*N")
for n = 1 to 25
$( let tot = totient(n)
let prime = n-1 = tot
if prime then count := count + 1
writef("%I2 %I7 %S*N", n, tot, prime -> " Yes", " No")
$)
writef("Number of primes up to %I6: %I4*N", 25, count)
for n = 26 to 10000
$( if totient(n) = n-1 then count := count + 1
if n = 100 | n = 1000 | n = 10000 then
writef("Number of primes up to %I6: %I4*N", n, count)
$)
$)</syntaxhighlight>
{{out}}
<pre> N Totient 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
Number of primes up to 25: 9
Number of primes up to 100: 25
Number of primes up to 1000: 168
Number of primes up to 10000: 1229</pre>
=={{header|BQN}}==
Line 1,867 ⟶ 1,995:
Number of primes up to 90000: 8713
Number of primes up to 100000: 9592</pre>
=={{header|COBOL}}==
<syntaxhighlight lang="cobol"> IDENTIFICATION DIVISION.
PROGRAM-ID. TOTIENT-FUNCTION.
DATA DIVISION.
WORKING-STORAGE SECTION.
01 TOTIENT-CALCULATION.
03 N PIC 9(6).
03 TOTIENT PIC 9(6).
03 DIVISOR PIC 9(6).
03 DIV-SQUARE PIC 9(6).
03 MODULUS PIC 9(6).
01 LOOP-VARS.
03 PRIME-COUNT PIC 9(4).
03 CURRENT-N PIC 9(6).
03 PRIME-TOTIENT PIC 9(6).
01 OUTPUTFORMAT.
03 HEADER PIC X(20) VALUE " N Totient Prime?".
03 TOTIENT-ROW.
05 OUT-N PIC Z9.
05 FILLER PIC XX VALUE SPACES.
05 OUT-TOTIENT PIC Z(6)9.
05 FILLER PIC XX VALUE SPACES.
05 OUT-PRIME PIC X(5).
03 PRIME-COUNT-ROW.
05 FILLER PIC X(22) VALUE "Number of primes up to".
05 OUT-PRMTO PIC Z(5)9.
05 FILLER PIC XX VALUE ": ".
05 OUT-PRMCNT PIC ZZZ9.
PROCEDURE DIVISION.
BEGIN.
MOVE ZERO TO PRIME-COUNT.
DISPLAY HEADER.
PERFORM SHOW-SMALL-TOTIENT
VARYING CURRENT-N FROM 1 BY 1
UNTIL CURRENT-N IS GREATER THAN 25.
MOVE 25 TO OUT-PRMTO.
MOVE PRIME-COUNT TO OUT-PRMCNT.
DISPLAY PRIME-COUNT-ROW.
PERFORM COUNT-PRIMES
VARYING CURRENT-N FROM 26 BY 1
UNTIL CURRENT-N IS GREATER THAN 10000.
STOP RUN.
SHOW-SMALL-TOTIENT.
MOVE CURRENT-N TO N.
PERFORM CALCULATE-TOTIENT.
MOVE CURRENT-N TO OUT-N.
MOVE TOTIENT TO OUT-TOTIENT.
MOVE "No" TO OUT-PRIME.
SUBTRACT 1 FROM CURRENT-N GIVING PRIME-TOTIENT.
IF TOTIENT IS EQUAL TO PRIME-TOTIENT,
MOVE "Yes" TO OUT-PRIME,
ADD 1 TO PRIME-COUNT.
DISPLAY TOTIENT-ROW.
COUNT-PRIMES.
MOVE CURRENT-N TO N.
PERFORM CALCULATE-TOTIENT.
SUBTRACT 1 FROM CURRENT-N GIVING PRIME-TOTIENT.
IF TOTIENT IS EQUAL TO PRIME-TOTIENT, ADD 1 TO PRIME-COUNT.
IF CURRENT-N IS EQUAL TO 100 OR 1000 OR 10000,
MOVE CURRENT-N TO OUT-PRMTO,
MOVE PRIME-COUNT TO OUT-PRMCNT,
DISPLAY PRIME-COUNT-ROW.
CALCULATE-TOTIENT.
MOVE N TO TOTIENT.
MOVE 2 TO DIVISOR.
MOVE 4 TO DIV-SQUARE.
PERFORM DIVIDE-STEP.
PERFORM DIVIDE-STEP
VARYING DIVISOR FROM 3 BY 2
UNTIL DIV-SQUARE IS GREATER THAN N.
IF N IS GREATER THAN 1,
COMPUTE TOTIENT = TOTIENT - TOTIENT / N.
DIVIDE-STEP.
MULTIPLY DIVISOR BY DIVISOR GIVING DIV-SQUARE.
DIVIDE N BY DIVISOR GIVING MODULUS.
MULTIPLY DIVISOR BY MODULUS.
SUBTRACT MODULUS FROM N GIVING MODULUS.
IF MODULUS IS ZERO,
PERFORM DIVIDE-OUT UNTIL MODULUS IS NOT ZERO,
COMPUTE TOTIENT = TOTIENT - TOTIENT / DIVISOR.
DIVIDE-OUT.
DIVIDE DIVISOR INTO N.
DIVIDE N BY DIVISOR GIVING MODULUS.
MULTIPLY DIVISOR BY MODULUS.
SUBTRACT MODULUS FROM N GIVING MODULUS.</syntaxhighlight>
{{out}}
<pre> N Totient 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
Number of primes up to 25: 9
Number of primes up to 100: 25
Number of primes up to 1000: 168
Number of primes up to 10000: 1229</pre>
=={{header|Cowgol}}==
Line 2,071 ⟶ 2,325:
=={{header|Delphi}}==
See [https://rosettacode.org/wiki/Totient_function#Pascal Pascal].
=={{header|Draco}}==
{{trans|C}}
<syntaxhighlight lang="draco">proc totient(word n) word:
word tot, i;
tot := n;
i := 2;
while i*i <= n do
if n%i = 0 then
while n%i = 0 do n := n/i od;
tot := tot - tot/i
fi;
if i=2 then i:=1 fi;
i := i+2
od;
if n>1 then
tot - tot/n
else
tot
fi
corp
proc main() void:
word count, n, tot;
bool prime;
count := 0;
writeln(" N Totient Prime");
for n from 1 upto 25 do
tot := totient(n);
prime := n-1 = tot;
if prime then count := count+1 fi;
writeln(n:2, " ", tot:7, " ", if prime then " Yes" else " No" fi)
od;
writeln("Number of primes up to ",25:6,": ",count:4);
for n from 25 upto 10000 do
if totient(n) = n-1 then count := count+1 fi;
if n=100 or n=1000 or n=10000 then
writeln("Number of primes up to ",n:6,": ",count:4)
fi
od
corp</syntaxhighlight>
{{out}}
<pre> N Totient 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
Number of primes up to 25: 9
Number of primes up to 100: 25
Number of primes up to 1000: 168
Number of primes up to 10000: 1229</pre>
=={{header|Dyalect}}==
Line 2,160 ⟶ 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,377 ⟶ 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,068 ⟶ 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 3,209 ⟶ 3,680:
1229
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;
FROM InOut IMPORT WriteString, WriteCard, WriteLn;
VAR count, n, tot: CARDINAL;
PROCEDURE totient(n: CARDINAL): CARDINAL;
VAR tot, i: CARDINAL;
BEGIN
tot := n;
i := 2;
WHILE i*i <= n DO
IF n MOD i = 0 THEN
WHILE n MOD i = 0 DO
n := n DIV i
END;
DEC(tot, tot DIV i)
END;
IF i=2 THEN i := 1 END;
INC(i, 2)
END;
IF n>1 THEN
DEC(tot, tot DIV n)
END;
RETURN tot
END totient;
PROCEDURE ShowPrimeCount(n, count: CARDINAL);
BEGIN
WriteString("Number of primes up to");
WriteCard(n, 6);
WriteString(": ");
WriteCard(count, 4);
WriteLn
END ShowPrimeCount;
BEGIN
count := 0;
WriteString(" N Totient Prime");
WriteLn;
FOR n := 1 TO 25 DO
tot := totient(n);
WriteCard(n, 2);
WriteCard(tot, 9);
IF tot = n-1 THEN
WriteString(" Yes");
INC(count)
ELSE
WriteString(" No")
END;
WriteLn
END;
ShowPrimeCount(25, count);
FOR n := 26 TO 10000 DO
IF totient(n) = n-1 THEN INC(count) END;
IF (n=100) OR (n=1000) OR (n=10000) THEN
ShowPrimeCount(n, count)
END;
END
END TotientFunction.</syntaxhighlight>
{{out}}
<pre> N Totient 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
Number of primes up to 25: 9
Number of primes up to 100: 25
Number of primes up to 1000: 168
Number of primes up to 10000: 1229</pre>
=={{header|Nim}}==
Line 3,578 ⟶ 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 3,651 ⟶ 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}}==
{{trans|C}}
<syntaxhighlight lang="plm">100H:
BDOS: PROCEDURE (F,A); DECLARE F BYTE, A ADDRESS; GO TO 5; END BDOS;
EXIT: PROCEDURE; GO TO 0; END EXIT;
PRINT: PROCEDURE (S); DECLARE S ADDRESS; CALL BDOS(9,S); END PRINT;
PRINT$NUM: PROCEDURE (N);
DECLARE (N, P) ADDRESS, CH BASED P BYTE;
DECLARE S (6) BYTE INITIAL ('.....$');
P = .S(5);
DIGIT:
P = P-1;
CH = '0' + N MOD 10;
IF (N := N/10) > 0 THEN GO TO DIGIT;
CALL PRINT(P);
END PRINT$NUM;
TOTIENT: PROCEDURE (N) ADDRESS;
DECLARE (TOT, N, I) ADDRESS;
TOT = N;
I = 2;
DO WHILE I*I <= N;
IF N MOD I = 0 THEN DO;
DO WHILE (N := N / I) MOD I = 0; END;
TOT = TOT - TOT / I;
END;
IF I=2 THEN I=1;
I = I+2;
END;
IF N > 1 THEN TOT = TOT - TOT / N;
RETURN TOT;
END TOTIENT;
SHOW$PRIME$COUNT: PROCEDURE (N, COUNT);
DECLARE (N, COUNT) ADDRESS;
CALL PRINT(.'THERE ARE $');
CALL PRINT$NUM(COUNT);
CALL PRINT(.' PRIMES UP TO $');
CALL PRINT$NUM(N);
CALL PRINT(.(13,10,'$'));
END SHOW$PRIME$COUNT;
DECLARE (N, TOT) ADDRESS;
DECLARE PRIME$COUNT ADDRESS INITIAL (0);
DO N = 1 TO 25;
CALL PRINT(.'PHI($');
CALL PRINT$NUM(N);
CALL PRINT(.') = $');
CALL PRINT$NUM(TOT := TOTIENT(N));
IF TOT = N-1 THEN DO;
CALL PRINT(.'; PRIME$');
PRIME$COUNT = PRIME$COUNT + 1;
END;
CALL PRINT(.(13,10,'$'));
END;
CALL SHOW$PRIME$COUNT(25, PRIME$COUNT);
DO N = 26 TO 10000;
IF TOTIENT(N) = N-1 THEN
PRIME$COUNT = PRIME$COUNT + 1;
IF N=100 OR N=1000 OR N=10000 THEN
CALL SHOW$PRIME$COUNT(N, PRIME$COUNT);
END;
CALL EXIT;
EOF</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|PicoLisp}}==
Line 3,762 ⟶ 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,342 ⟶ 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 4,721 ⟶ 5,584:
{{trans|Go}}
{{libheader|Wren-fmt}}
<syntaxhighlight lang="
var totient = Fn.new { |n|
| |||