RosettaCodeData/Task/Totient-function/ALGOL-M/totient-function.alg

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