nvec ← ##.sieve nvec                    ⍝ Sieve of Eratosthenes
                                        ⍝ Eratosthenes of Cyrene (¯276-¯194)

Removes multiples of numbers within the argument vector. Thus sieve 2..⍵ returns
those  primes in the range 2..⍵.  An illustration of most of the D-function con-
structs: left argument defaulting; local definition; guards; tail recursion.

(muse:

    Among other accomplishments, Eratosthenes estimated the circumference of the
    Earth to a surprising accuracy.

    http://en.wikipedia.org/wiki/Eratosthenes  reports Eratasthenes' estimate to
    be 16% too large, taking the value of the stadion to be 185m. However, if we
    take  a  value  of  157.2, which some people derive from Pliny, the estimate
    comes in at only 3% too small.
)

Roger Hui provides this more efficient coding, which returns a boolean vector.
It assumes an index origin of 0:

    ⎕io←0

    sieve←{
      b←⍵⍴{∧⌿↑(×/⍵)⍴¨~⍵↑¨1}2 3 5
      b[⍳6⌊⍵]←(6⌊⍵)⍴0 0 1 1 0 1
      49≥⍵:b
      p←3↓⍸∇⌈⍵*0.5
      m←1+⌊(⍵-1+p×p)÷2×p
      b⊣p{b[⍺×⍺+2×⍳⍵]←0}¨m
    }

    sieve 40        ⍝ primes less than 40
0 0 1 1 0 1 0 1 0 0 0 1 0 1 0 0 0 1 0 1 0 0 0 1 0 0 0 0 0 1 0 1 0 0 0 0 0 1 0 0

    ⍸ sieve 40
2 3 5 7 11 13 17 19 23 29 31 37

(muse:

    A succinct way to express the vector of prime numbers up to (say) 100 is:

          (~v∊v∘.×v)/v←1↓⍳100           ⍝ primes to 100.
    2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97

    This expression may be read left-to-right as: "Those items of v that are not
    in the  product-table of v,  where v is a vector of all but the first of the
    numbers from 1 to 100."

        (~ v ∊ v ∘.× v) / v ← 1 ↓ ⍳100
         │   │ └──┬──┘  └┬┘ │ └┬┘ └┬─┘
         │   │    │      └────────────────Those items of v that
         │   │    │         │  │   │
         └────────────────────────────────are not
             │    │         │  │   │
             └────────────────────────────in
                  │         │  │   │
                  └───────────────────────the product table of v,
                            │  │   │
                            └─────────────where v is a vector of
                               │   │
                               └──────────all but the first of
                                   │
                                   └──────the numbers from 1 to 100.

    Note however, that this is an O(n*2) algorithm in both space and time and so
    is infeasible for large arguments.

    A criticism that the APL language encourages "over computation",  in that it
    leads us into calculating many more values than are required,  is misdirect-
    ed.  The  _language_ has no interest in which values are actually calculated
    and a smart, lazy implementation might well avoid creating (parts of) inter-
    mediate arrays.
)

Example:

    sieve 2 to 100
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97

See also: pco to

Back to: contents

Back to: Workspaces