Sieve of Eratosthenes (Forth)
- Other implementations: Alice ML | Bash | C++ | Forth | Haskell | Java | Python | Python, arrays | Scala
The Sieve of Eratosthenes is an algorithm for rapidly locating all the prime numbers in a certain range of integers. It operates by marking as composite all nontrivial multiples of each prime in sequence until only primes remain unmarked. It is most well-suited to implementation using arrays, which are compact and feature random access.
This program counts the number of primes up to 7919 (the 1000th prime) using the Sieve of Eratosthenes. The algorithm is optimized by assuming 2 is prime, and thus only examining odd numbers.
( dup .) can be uncommented to list the primes found.
<<sieve.fs>>= 7919 2/ CONSTANT maxp \ 2/ because we only count odd primes : PRIMES ( -- n ) HERE maxp 1 FILL 1 ( count, including 2 ) maxp 0 DO I HERE + C@ IF I 2* 3 + ( dup .) DUP I + ( prime current ) BEGIN DUP maxp U< WHILE 0 OVER HERE + C! OVER + REPEAT 2DROP 1+ THEN LOOP ; PRIMES . \ 1000