Totient function: Difference between revisions

=={{header|ALGOL 68}}==

{{Trans|Go}}

Uses the totient algorithm from the second Go sample.

<lang algol68>BEGIN

# returns the number of integers k where 1 <= k <= n that are mutually prime to n #

PROC totient = ( INT n )INT:

IF n < 3 THEN 1

ELIF n = 3 THEN 2

ELSE

INT result := n;

INT v := n;

INT i := 2;

WHILE i * i <= v DO

IF v MOD i = 0 THEN

WHILE v MOD i = 0 DO v OVERAB i OD;

result -:= result OVER i

FI;

IF i = 2 THEN

i := 1

FI;

i +:= 2

OD;

IF v > 1 THEN result -:= result OVER v FI;

result

FI # totient # ;

# show the totient function values for the first 25 integers #

print( ( " n phi(n) remarks", newline ) );

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 #

INT n100 := 0, n1000 := 0, n10000 := 0, n100000 := 0;

FOR n TO 100 000 DO

IF totient( n ) = n - 1 THEN

IF n <= 100 THEN n100 +:= 1 FI;

IF n <= 1 000 THEN n1000 +:= 1 FI;

IF n <= 10 000 THEN n10000 +:= 1 FI;

IF n <= 100 000 THEN n100000 +:= 1 FI

FI

OD;

print( ( "There are ", whole( n100, -6 ), " primes below 100", newline ) );

print( ( "There are ", whole( n1000, -6 ), " primes below 1 000", newline ) );

print( ( "There are ", whole( n10000, -6 ), " primes below 10 000", newline ) );

print( ( "There are ", whole( n100000, -6 ), " primes below 100 000", newline ) )

END</lang>

{{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>