58 lines
1.1 KiB
Plaintext
58 lines
1.1 KiB
Plaintext
$lines
|
|
|
|
rem - return p mod q
|
|
function mod(p, q = integer) = integer
|
|
end = p - q * (p / q)
|
|
|
|
rem - return greatest common divisor of x and y
|
|
function gcd(x, y = integer) = integer
|
|
var r, temp = integer
|
|
if x < y then
|
|
begin
|
|
temp = x
|
|
x = y
|
|
y = temp
|
|
end
|
|
r = mod(x, y)
|
|
while r <> 0 do
|
|
begin
|
|
x = y
|
|
y = r
|
|
r = mod(x, y)
|
|
end
|
|
end = y
|
|
|
|
rem - return phi (also called totient) of n
|
|
function phi(n = integer) = integer
|
|
var i, count = integer
|
|
count = 1
|
|
for i = 2 to n
|
|
if gcd(n, i) = 1 then count = count + 1
|
|
next i
|
|
end = count
|
|
|
|
rem - exercise the function
|
|
var n, totient, count = integer
|
|
print " n Phi(n) Prime?"
|
|
for n = 1 to 25
|
|
totient = phi(n)
|
|
print using "#### #### ";n, totient;
|
|
if totient + 1 = n then
|
|
print "yes"
|
|
else
|
|
print "no"
|
|
next n
|
|
|
|
rem - and further test it by counting primes
|
|
print
|
|
count = 0
|
|
for n = 1 to 1000
|
|
if phi(n) = n - 1 then count = count + 1
|
|
if n = 100 then
|
|
print "Primes up to 100 = ";count
|
|
else if n = 1000 then
|
|
print "Primes up to 1000 = ";count
|
|
next n
|
|
|
|
end
|