66 lines
1.1 KiB
Plaintext
66 lines
1.1 KiB
Plaintext
BEGIN
|
|
|
|
% RETURN P MOD Q %
|
|
INTEGER FUNCTION MOD (P, Q);
|
|
INTEGER P, Q;
|
|
BEGIN
|
|
MOD := P - Q * (P / Q);
|
|
END;
|
|
|
|
% RETURN GREATEST COMMON DIVISOR OF X AND Y %
|
|
INTEGER FUNCTION GCD (X, Y);
|
|
INTEGER X, Y;
|
|
BEGIN
|
|
INTEGER R;
|
|
IF X < Y THEN
|
|
BEGIN
|
|
INTEGER TEMP;
|
|
TEMP := X;
|
|
X := Y;
|
|
Y := TEMP;
|
|
END;
|
|
WHILE (R := MOD(X, Y)) <> 0 DO
|
|
BEGIN
|
|
X := Y;
|
|
Y := R;
|
|
END;
|
|
GCD := Y;
|
|
END;
|
|
|
|
% RETURN PHI (ALSO CALLED TOTIENT) OF N %
|
|
INTEGER FUNCTION PHI(N);
|
|
INTEGER N;
|
|
BEGIN
|
|
INTEGER I, COUNT;
|
|
COUNT := 1;
|
|
FOR I := 2 STEP 1 UNTIL N DO
|
|
BEGIN
|
|
IF GCD(N,I) = 1 THEN COUNT := COUNT + 1;
|
|
END;
|
|
PHI := COUNT;
|
|
END;
|
|
|
|
COMMENT - EXERCISE THE FUNCTION;
|
|
INTEGER N, TOTIENT, COUNT;
|
|
WRITE(" N PHI(N) PRIME?");
|
|
FOR N := 1 STEP 1 UNTIL 25 DO
|
|
BEGIN
|
|
WRITE(N, (TOTIENT := PHI(N)));
|
|
WRITEON(IF TOTIENT = (N-1) THEN " YES" ELSE " NO");
|
|
END;
|
|
|
|
COMMENT - AND USE IT TO COUNT PRIMES;
|
|
WRITE("");
|
|
COUNT := 0;
|
|
FOR N := 1 STEP 1 UNTIL 1000 DO
|
|
BEGIN
|
|
IF PHI(N) = (N-1) THEN COUNT := COUNT + 1;
|
|
IF N = 100 THEN
|
|
WRITE("PRIMES UP TO 100 =", COUNT)
|
|
ELSE IF N = 1000 THEN
|
|
WRITE("PRIMES UP TO 1000 =", COUNT);
|
|
END;
|
|
|
|
|
|
END
|