Talk:ALGOL 68-primes: Difference between revisions
Content added Content deleted
(→Source code: Include 0 in the sieve) |
(→Source code: Added operators, etc. for extracting a list of primes from a sieve of primes) |
||
Line 12: | Line 12: | ||
FOR i FROM 4 BY 2 TO UPB prime DO prime[ i ] := FALSE OD; |
FOR i FROM 4 BY 2 TO UPB prime DO prime[ i ] := FALSE OD; |
||
FOR i FROM 3 BY 2 TO ENTIER sqrt( UPB prime ) DO |
FOR i FROM 3 BY 2 TO ENTIER sqrt( UPB prime ) DO |
||
IF prime[ i ] THEN |
IF prime[ i ] THEN |
||
FOR s FROM i * i BY i + i TO UPB prime DO prime[ s ] := FALSE OD |
|||
FI |
|||
OD; |
OD; |
||
prime |
prime |
||
END; # PRIMESIEVE # |
END; # PRIMESIEVE # |
||
# modes and operators for extracting primes from a sieve # |
|||
INT first n primes extract op = 0; |
|||
INT primes up to extract op = 1; |
|||
MODE PRIMEEXTRACT = STRUCT( INT extract op, INT n ); |
|||
# returns a PRIMEEXTRACT with the first n primces extract op # |
|||
OP EXTRACTFIRST = ( INT n )PRIMEEXTRACT: PRIMEEXTRACT( first n primes extract op, n ); |
|||
# returns a PRIMEEXTRACT with primes up to extract op # |
|||
OP EXTRACTPRIMESUPTO = ( INT n )PRIMEEXTRACT: PRIMEEXTRACT( primes up to extract op, n ); |
|||
# returns an array of primes extracted from prime # |
|||
# as specified by by the extract op and number of primes in ex # |
|||
PRIO PRIMESFROMSIEVE = 9, FROMPRIMESIEVE = 9; |
|||
OP PRIMESFROMSIEVE = ( PRIMEEXTRACT ex, []BOOL prime )[]INT: |
|||
IF extract op OF ex = first n primes extract op |
|||
THEN |
|||
# extract the first n OF ex primes # |
|||
# count the primes up n OF ex # |
|||
INT p count := 0; |
|||
FOR i TO UPB prime WHILE p count < n OF ex DO |
|||
IF prime[ i ] THEN p count +:= 1 FI |
|||
OD; |
|||
# construct a list of the first n OF ex primes or p count, # |
|||
# whichever is smaller # |
|||
[ 1 : p count ]INT low prime; |
|||
INT low pos := 0; |
|||
FOR i WHILE low pos < UPB low prime DO |
|||
IF prime[ i ] THEN low prime[ low pos +:= 1 ] := i FI |
|||
OD; |
|||
low prime |
|||
ELSE |
|||
# extract primes up to n OF ex primes # |
|||
INT max prime = n OF ex; |
|||
# count the primes up to max prime # |
|||
INT p count := 0; |
|||
FOR i TO max prime DO IF prime[ i ] THEN p count +:= 1 FI OD; |
|||
# construct a list of the primes up to max prime # |
|||
[ 1 : p count ]INT low prime; |
|||
INT low pos := 0; |
|||
FOR i WHILE low pos < UPB low prime DO |
|||
IF prime[ i ] THEN low prime[ low pos +:= 1 ] := i FI |
|||
OD; |
|||
low prime |
|||
FI # PRIMESFROMSIEVE # ; |
|||
# alternative spelling of the operator name # |
|||
OP FROMPRIMESIEVE = ( PRIMEEXTRACT ex, []BOOL prime )[]INT: ex PRIMESFROMSIEVE prime; |
|||
# END primes.incl.a68 #</lang> |
# END primes.incl.a68 #</lang> |