Totient function: Difference between revisions
Content added Content deleted
(Added Algol 68) |
(Undo revision 335807 by Tigerofdarkness (talk)) |
||
Line 212: | Line 212: | ||
Number of primes up to 90000 = 8713 |
Number of primes up to 90000 = 8713 |
||
Number of primes up to 100000 = 9592</pre> |
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}}== |
=={{header|AWK}}== |