MODULE LegendrePi;     (* Legendre prime counting function                   *)
                       (* - translation of EasyLang/Go non-memoised version  *)
    IMPORT Primes, Math, Out;

    CONST  maxPrime             = 32000;   (* somewhat more than sqrt( 1e9 ) *)
    VAR    primeSieve           : ARRAY maxPrime OF BOOLEAN;
           primeList            : ARRAY maxPrime OF INTEGER;

    PROCEDURE pi( n : INTEGER ) : INTEGER;
        VAR     rootN, result   : INTEGER;

        PROCEDURE phi( x, aIn : INTEGER; primes : ARRAY OF INTEGER ) : INTEGER;
            VAR   a, sum, pa, count  : INTEGER;
                  found1             : BOOLEAN;
            BEGIN
                a      := aIn;
                sum    := 0;
                found1 := FALSE;
                WHILE ( a > 1 ) & ~ found1 DO
                    pa := primes[ a ];
                    IF x <= pa THEN
                        found1 := TRUE
                    ELSE
                        DEC( a );
                        INC( sum, phi( x DIV pa, a, primes ) )
                    END
                END;
                IF found1 THEN count := 1 ELSE count := x - ( x DIV 2 ) - sum END
            RETURN count
            END phi;

        BEGIN
            IF    n < 2 THEN result := 0
            ELSIF n = 2 THEN result := 1
            ELSE
                rootN := FLOOR( Math.sqrt( FLT( n ) ) );
                Primes.extractUpTo( rootN, primeList, primeSieve );
                result := phi( n, primeList[ 0 ], primeList ) + primeList[ 0 ] - 1
            END
        RETURN result
        END pi;

    PROCEDURE showPiForPowersOfTen;
        VAR   i, n    : INTEGER;
        BEGIN
            n := 1;
            FOR i := 0 TO 9 DO
                Out.String( "10^" );Out.Int( i, 0 );Out.String( "  " );Out.Int( pi( n ), 0 );Out.Ln;
                n := n * 10
            END
        END showPiForPowersOfTen;

BEGIN
    Primes.sieve( primeSieve );
    showPiForPowersOfTen
END LegendrePi.