Sieve of Eratosthenes (Forth)

From LiteratePrograms

Jump to: navigation, search
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 is a code dump.
Code dumps are articles with little or no documentation or rearrangement of code. Please help to turn it into a literate program. Also make sure that the source of this code does consent to release it under the MIT or public domain license.


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
Download code
Retrieved from "http://literateprograms.org/Sieve_of_Eratosthenes_%28Forth%29"
Views