Rosetta Code

Totient function: Difference between revisions

Page Discussion

Totient function (view source)

Revision as of 15:09, 14 February 2024

28,654 bytes added ,  3 months ago
m
→‎{{header|Wren}}: Minor tidy
m (→‎{{header|Wren}}: Minor tidy)
 
(25 intermediate revisions by 10 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 ) )
, 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;
COUNT := 1;
FOR I := 2 STEP 1 UNTIL N DO
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
WRITE(N, (TOTIENT := PHI(N)));
WRITEON(IF TOTIENT = (N-1) THEN " YES" ELSE " NO");
END;
 
Line 777 ⟶ 780:
IF N = 100 THEN
WRITE("PRIMES UP TO 100 =", COUNT)
ELSE IF N = 1000 THEN
WRITE("PRIMES UP TO 1000 =", COUNT);
END;
Line 1,226 ⟶ 1,229:
Number of primes to 100000 : 9592
</pre>
 
=={{header|Arturo}}==
 
<syntaxhighlight lang="arturo">totient: function [n][
tot: new n
i: 2
while -> n >= i * i [
if 0 = n % i [
while -> 0 = n % i -> n: n / i
'tot - tot / i
]
if 2 = i -> i: 1
'i + 2
]
if n > 1 -> 'tot - tot / n
return tot
]
 
primes: 0
loop 1..100000 'i [
t: totient i
prime?: 1 = i - t
if i < 26 [
prints ~« Φ(|pad.with:`0` to :string i 2|) = |pad to :string t 2|
if prime? -> prints ", prime"
print ""
]
if 50 = i -> print ""
if in? i [100 1000 10000 100000] -> print ~« |primes| primes =< |i|
if prime? -> 'primes + 1
]</syntaxhighlight>
 
{{out}}
 
<pre>Φ(01) = 1
Φ(02) = 1, prime
Φ(03) = 2, prime
Φ(04) = 2
Φ(05) = 4, prime
Φ(06) = 2
Φ(07) = 6, prime
Φ(08) = 4
Φ(09) = 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
 
25 primes =< 100
168 primes =< 1000
1229 primes =< 10000
9592 primes =< 100000</pre>
 
=={{header|AutoHotkey}}==
Line 1,280 ⟶ 1,347:
totalPrimes := principal(100)
msgbox % "total primes in 1 .. 100 = " totalPrimes
totalPrimes := principal(1000) ; caution... pure gcd method
msgbox % "total primes in 1 .. 1000 = " totalPrimes ; takes 3 minutes or more
;totalPrimes := principal(10000)
;msgbox % "total primes in 1 .. 10000 = " totalPrimes
Line 1,330 ⟶ 1,397:
---------------------------
OK
</pre>
 
=={{header|AWK}}==
Line 1,410 ⟶ 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,709 ⟶ 1,902:
Count of primes up to 10000000: 664579
</pre>
 
=={{header|CLU}}==
{{trans|C}}
<syntaxhighlight lang="clu">totient = proc (n: int) returns (int)
tot: int := n
 
i: int := 2
while i*i <= n do
if n//i = 0 then
while n//i = 0 do
n := n/i
end
tot := tot-tot/i
end
if i=2 then i:=1 end
i := i+2
end
if n>1 then
tot := tot-tot/n
end
return(tot)
end totient
 
start_up = proc ()
po: stream := stream$primary_output()
count: int := 0
 
stream$putl(po, " N Totient Prime")
for n: int in int$from_to(1, 25) do
tot: int := totient(n)
stream$putright(po, int$unparse(n), 2)
stream$putright(po, int$unparse(tot), 9)
if n-1 = tot then
stream$putright(po, "Yes", 7)
count := count + 1
else
stream$putright(po, "No", 7)
end
stream$putl(po, "")
end
 
stream$putl(po, "Number of primes up to 25:\t" || int$unparse(count))
for n: int in int$from_to(26, 100000) do
if totient(n) = n-1 then
count := count + 1
end
if n = 100 cor n = 1000 cor n // 10000 = 0 then
stream$putl(po, "Number of primes up to "
|| int$unparse(n) || ":\t"
|| int$unparse(count))
end
end
end start_up</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
Number of primes up to 20000: 2262
Number of primes up to 30000: 3245
Number of primes up to 40000: 4203
Number of primes up to 50000: 5133
Number of primes up to 60000: 6057
Number of primes up to 70000: 6935
Number of primes up to 80000: 7837
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}}==
{{trans|C}}
<syntaxhighlight lang="cowgol">include "cowgol.coh";
 
sub totient(n: uint32): (tot: uint32) is
tot := n;
 
var i: uint32 := 2;
while i*i <= n loop
if n%i == 0 then
while n%i == 0 loop
n := n/i;
end loop;
tot := tot - tot/i;
end if;
if i == 2 then
i := 1;
end if;
i := i + 2;
end loop;
 
if n > 1 then
tot := tot - tot/n;
end if;
end sub;
 
var count: uint16 := 0;
 
print("N\tTotient\tPrime\n");
var n: uint32 := 1;
while n <= 25 loop
var tot := totient(n);
print_i32(n);
print_char('\t');
print_i32(tot);
print_char('\t');
if n-1 == tot then
count := count + 1;
print("Yes\n");
else
print("No\n");
end if;
n := n + 1;
end loop;
 
print("Number of primes up to 25:\t");
print_i16(count);
print_nl();
 
while n <= 100000 loop
tot := totient(n);
if n-1 == tot then
count := count + 1;
end if;
if n == 100 or n == 1000 or n % 10000 == 0 then
print("Number of primes up to ");
print_i32(n);
print(":\t");
print_i16(count);
print_nl();
end if;
n := n + 1;
end loop;</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
Number of primes up to 20000: 2262
Number of primes up to 30000: 3245
Number of primes up to 40000: 4203
Number of primes up to 50000: 5133
Number of primes up to 60000: 6057
Number of primes up to 70000: 6935
Number of primes up to 80000: 7837
Number of primes up to 90000: 8713
Number of primes up to 100000: 9592</pre>
 
=={{header|D}}==
Line 1,809 ⟶ 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 1,898 ⟶ 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,114 ⟶ 2,749:
=={{header|Fōrmulæ}}==
 
{{FormulaeEntry|page=https://formulae.org/?script=examples/Euler%27s_totient_function}}
Fōrmulæ programs are not textual, visualization/edition of programs is done showing/manipulating structures but not text. Moreover, there can be multiple visual representations of the same program. Even though it is possible to have textual representation &mdash;i.e. XML, JSON&mdash; they are intended for storage and transfer purposes more than visualization and edition.
 
'''Solution'''
Programs in Fōrmulæ are created/edited online in its [https://formulae.org website], However they run on execution servers. By default remote servers are used, but they are limited in memory and processing power, since they are intended for demonstration and casual use. A local server can be downloaded and installed, it has no limitations (it runs in your own computer). Because of that, example programs can be fully visualized and edited, but some of them will not run if they require a moderate or heavy computation/memory resources, and no local server is being used.
 
[[File:Fōrmulæ - Totient function 01.png]]
In '''[https://formulae.org/?example=Euler%27s_totient_function this]''' page you can see the program(s) related to this task and their results.
 
'''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 2,811 ⟶ 3,458:
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}}==
{{trans|C}}
<syntaxhighlight lang="mad"> NORMAL MODE IS INTEGER
BOOLEAN PRM
 
INTERNAL FUNCTION(A,B)
ENTRY TO REM.
FUNCTION RETURN A-A/B*B
END OF FUNCTION
 
INTERNAL FUNCTION(NN)
ENTRY TO TOTENT.
N = NN
TOT = N
THROUGH STEP, FOR I=2, 2, I*I.G.N
WHENEVER REM.(N,I).E.0
THROUGH DIV, FOR N=N, 0, REM.(N,I).NE.0
DIV N = N/I
TOT = TOT-TOT/I
END OF CONDITIONAL
WHENEVER I.E.2, I=1
STEP CONTINUE
WHENEVER N.G.1, TOT = TOT-TOT/N
FUNCTION RETURN TOT
END OF FUNCTION
 
COUNT = 0
PRINT FORMAT HEADER
THROUGH FRST25, FOR KN=1, 1, KN.G.25
KTOT = TOTENT.(KN)
PRM = KTOT.E.KN-1
WHENEVER PRM, COUNT = COUNT + 1
FRST25 PRINT FORMAT NUMTOT,KN,KTOT,PRM
 
PRINT FORMAT NUMPRM,25,COUNT
 
THROUGH CNTPRM, FOR KN=26, 1, KN.G.100000
KTOT = TOTENT.(KN)
WHENEVER KTOT.E.KN-1, COUNT = COUNT+1
WHENEVER KN.E.100 .OR. KN.E.1000 .OR. REM.(KN,10000).E.0,
0 PRINT FORMAT NUMPRM,KN,COUNT
CNTPRM CONTINUE
 
VECTOR VALUES HEADER = $19H N TOTIENT PRIME*$
VECTOR VALUES NUMTOT = $I2,S2,I7,S2,I5*$
VECTOR VALUES NUMPRM = $22HNUMBER OF PRIMES UP TO,I7,1H:,I6*$
END OF PROGRAM</syntaxhighlight>
{{out}}
<pre> N TOTIENT PRIME
1 1 0
2 1 1
3 2 1
4 2 0
5 4 1
6 2 0
7 6 1
8 4 0
9 6 0
10 4 0
11 10 1
12 4 0
13 12 1
14 6 0
15 8 0
16 8 0
17 16 1
18 6 0
19 18 1
20 8 0
21 12 0
22 10 0
23 22 1
24 8 0
25 20 0
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
NUMBER OF PRIMES UP TO 20000: 2262
NUMBER OF PRIMES UP TO 30000: 3245
NUMBER OF PRIMES UP TO 40000: 4203
NUMBER OF PRIMES UP TO 50000: 5133
NUMBER OF PRIMES UP TO 60000: 6057
NUMBER OF PRIMES UP TO 70000: 6935
NUMBER OF PRIMES UP TO 80000: 7837
NUMBER OF PRIMES UP TO 90000: 8713
NUMBER OF PRIMES UP TO 100000: 9592</pre>
=={{header|Mathematica}} / {{header|Wolfram Language}}==
<syntaxhighlight lang="mathematica">Do[
Line 2,864 ⟶ 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,233 ⟶ 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,306 ⟶ 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,417 ⟶ 4,560:
=={{header|Quackery}}==
 
<code>gcd</code> is defined at [[Greatest common divisor#Quackery]].
<syntaxhighlight lang="quackery "> [ [ dup while
tuck mod again ]
drop abs ] is gcd ( n n --> n )
 
 
<syntaxhighlight lang="quackery "> [ 0 swap dup times
[ i over gcd
1 = rot + swap ]
Line 3,735 ⟶ 4,875:
 
def 𝜑(n)
n.prime_division.inject(1) {|res, (pr, exp)| res *= (pr-1) * pr**(exp-1) }
end
 
Line 3,997 ⟶ 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,376 ⟶ 5,584:
{{trans|Go}}
{{libheader|Wren-fmt}}
<syntaxhighlight lang="ecmascriptwren">import "./fmt" for Fmt
 
var totient = Fn.new { |n|
PureFox
9,476

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/335853...353687"