Dyalog APL - Sieve of Eratosthenes

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

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

(muse:

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

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

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

⎕io←0

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

sieve 40 ⍝ primes less than 40<br>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<br>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.<br>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<br>in the product-table of v, where v is a vector of all but the first of the<br>numbers from 1 to 100."

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

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

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

Example:

sieve 2 to 100<br>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