36 lines
1.2 KiB
Text
36 lines
1.2 KiB
Text
BEGIN # Legendre prime counting function - translation of EasyLang/Go non-memoised version #
|
|
|
|
PR read "primes.incl.a68" PR # include RC prime utilities #
|
|
|
|
OP PI = ( INT n )INT:
|
|
IF n < 2 THEN 0
|
|
ELIF n = 2 THEN 1
|
|
ELSE
|
|
INT root n = ENTIER sqrt( n );
|
|
[]INT primes = EXTRACTPRIMESUPTO root n FROMPRIMESIEVE PRIMESIEVE root n;
|
|
INT prime count = UPB primes;
|
|
|
|
PROC phi = ( INT x, a in )INT:
|
|
BEGIN
|
|
INT a := a in, sum := 0;
|
|
BOOL continue := TRUE;
|
|
WHILE a > 1 AND continue DO
|
|
INT pa = primes[ a ];
|
|
IF x <= pa THEN
|
|
continue := FALSE
|
|
ELSE
|
|
a -:= 1;
|
|
sum +:= phi( x OVER pa, a )
|
|
FI
|
|
OD;
|
|
IF continue THEN x - ( x OVER 2 ) - sum ELSE 1 FI
|
|
END;
|
|
|
|
phi( n, prime count ) + prime count - 1
|
|
FI;
|
|
|
|
FOR i FROM 0 TO 9 DO
|
|
INT n = 10 ^ i;
|
|
print( ( "10^", whole( i, 0 ), " ", whole( PI n, 0 ), newline ) )
|
|
OD
|
|
END
|