56 lines
1.9 KiB
Text
56 lines
1.9 KiB
Text
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.
|