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