Totient function: Difference between revisions
Added Algol 68
No edit summary |
(Added Algol 68) |
||
Line 212:
Number of primes up to 90000 = 8713
Number of primes up to 100000 = 9592</pre>
=={{header|ALGOL 68}}==
<lang algol68>BEGIN
# iterative Greatest Common Divisor routine, returns the gcd of m and n #
PROC gcd = ( INT m, n )INT:
BEGIN
INT a := ABS m, b := ABS n;
WHILE b /= 0 DO
INT new a = b;
b := a MOD b;
a := new a
OD;
a
END # gcd # ;
# returns the number of integers k where 1 <= k <= n that are mutually prime to n #
PROC totient = ( INT n )INT:
BEGIN
INT result := 0;
FOR k TO n DO
IF gcd( n, k ) = 1 THEN
# n and k are mutually prime #
result +:= 1
FI
OD;
result
END # 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;
FOR n TO 10 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
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 ) )
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
</pre>
=={{header|AWK}}==
| |||