47 lines
1.6 KiB
Plaintext
47 lines
1.6 KiB
Plaintext
scope # Totient function
|
|
|
|
# returns the number of integers k where 1 <= k <= n that are mutually prime to n
|
|
local procedure totient( n :: number ) :: number
|
|
if n < 3 then result := 1
|
|
elif n = 3 then result := 2
|
|
else
|
|
result := n;
|
|
local v, i := n, 2;
|
|
while i * i <= v do
|
|
if v mod i = 0 then
|
|
while v mod i = 0 do v \:= i od;
|
|
result -:= result \ i
|
|
fi;
|
|
if i = 2 then
|
|
i := 1
|
|
fi;
|
|
i +:= 2
|
|
od;
|
|
if v > 1 then result -:= result \ v fi;
|
|
fi;
|
|
return result
|
|
end;
|
|
|
|
# show the totient function values for the first 25 integers
|
|
io.write( " n phi(n) remarks\n" );
|
|
for n to 25 do
|
|
local constant tn := totient( n );
|
|
printf( "%2d: %5d%s\n", n, tn, if tn = n - 1 and tn <> 0 then " n is prime" else "" fi )
|
|
od;
|
|
|
|
# use the totient function to count primes
|
|
local n100, n1_000, n10_000, n100_000 := 0, 0, 0, 0;
|
|
for n to 100_000 do
|
|
if totient( n ) = n - 1 then
|
|
if n <= 100 then n100 +:= 1 fi;
|
|
if n <= 1000 then n1_000 +:= 1 fi;
|
|
if n <= 10000 then n10_000 +:= 1 fi;
|
|
if n <= 100000 then n100_000 +:= 1 fi
|
|
fi
|
|
od;
|
|
printf( "There are %6d primes below 100\n", n100 );
|
|
printf( "There are %6d primes below 1 000\n", n1_000 );
|
|
printf( "There are %6d primes below 10 000\n", n10_000 );
|
|
printf( "There are %6d primes below 100 000\n", n100_000 )
|
|
end
|