Square-free integers: Difference between revisions
→{{header|ALGOL 68}}: Optimise
(→{{header|ALGOL 68}}: fixed comment) |
(→{{header|ALGOL 68}}: Optimise) |
||
Line 35:
<lang algol68>BEGIN
# count/show some square free numbers #
# a number
# by any squared prime #
# to satisfy the task we need to know the primes up to root 1 000 000 000 145 #
# and the square free numbers up to 1 000 000 #
# sieve the primes #
LONG INT
[ prime max ]BOOL prime; FOR i TO UPB prime DO prime[ i ] := TRUE OD;
FOR s FROM 2 TO ENTIER sqrt( sieve max ) DO▼
FOR s FROM 2
IF prime[ s ] THEN
FOR p FROM s * s BY s TO
OD;
# sieve the square free integers #
INT sf max = 1 000 000;
[ sf max ]BOOL square free;FOR i TO UPB square free DO square free[ i ] := TRUE OD;
IF prime[ s ] THEN
INT q = s * s;
FOR p FROM q BY q TO sf max DO square free[ p ] := FALSE OD
FI
OD;
# returns TRUE if n is square free, FALSE otherwise #
PROC is square free = ( LONG INT n )BOOL:
IF n <= sf max THEN square free[ SHORTEN n ]
▲ BEGIN
ELSE
# n is larger than the sieve - use trial division #
INT max factor = ENTIER SHORTEN long sqrt( n ) + 1;
BOOL square free := TRUE;
FOR f FROM 2 TO max factor WHILE square free DO
IF
# have a prime #
square free := ( n MOD ( LENG f * LENG f ) /= 0 )
Line 57 ⟶ 71:
OD;
square free
# returns the count of square free numbers between m and n (inclusive) #
PROC count square free = ( INT m, n )INT:
BEGIN
INT count := 0;
FOR i FROM m TO n DO IF
count
END # count square free # ;
Line 81 ⟶ 95:
print( ( "Square free numbers from 1 000 000 000 000 to 1 000 000 000 145", newline ) );
count := 0;
FOR i FROM 0 TO 145 DO▼
▲ FOR i TO 145 DO
IF is square free( one trillion + i ) THEN
print( ( whole( one trillion + i, -14 ) ) );
| |||