fwiw, I cribbed some Python code a while ago to achieve a pretty fast J function.
Unfortunately, I haven't kept a reference to its source, although I do have notes explaining the algorithm. Virtually the same code may be used to derive the sum of primes less than some limit. Perhaps surprisingly, it does not identify all the primes in the range, so is more efficient than a sieve for largish limits. I can provide further details if required. But for now, here's a glimpse at the performance on my machine, compared to Roger's sieve method as reported in http://www.jsoftware.com/papers/50/ chapter 46. I've coded Roger's APL-function in J as HuiSieve50, available if required. NB. lHS = 10 to force it to calculate, otherwise it just uses _1 p: which NB. defeats the purpose (!) NB. {.{: because my function currently produces an interesting (?) array. timer'{.{:10 primepi 10000000' NB. ie 10^7 +---------+------+ |0.0410004|664579| +---------+------+ timer'+/HuiSieve50 10000000' +-----+------+ |0.389|664579| +-----+------+ ts'{.{:10 primepi 10000000' NB. time and space 0.0459825 659712 ts'+/HuiSieve50 10000000' 0.416195 3.35707e7 timer'{.{:10 primepi 100000000' NB. ie 10^8 +--------+-------+ |0.126999|5761455| +--------+-------+ timer'+/HuiSieve50 100000000' +-----+-------+ |3.959|5761455| +-----+-------+ NB. And here's the answer to Roger's challenge: timer'{.{:10 primepi <.1e9' +--------+--------+ |0.607002|50847534| +--------+--------+ NB. similar for sum of primes: timer' {.{:sumprime 100000000' +---------+---------------+ |0.0890045|279209790387276| +---------+---------------+ timer'+/I.HuiSieve50 100000000' +-----+---------------+ |3.765|279209790387276| +-----+---------------+ (Meissel)-Lehmer is supposed to be good; my attempt to code it in J yielded a slower function than my "primepi" , but that may well be my poor understanding and/or J-translation ! Please note, if you go to the Mathematica Page in pursuit of Lehmer's primepi, http://mathworld.wolfram.com/LehmersFormula.html that the limits 1 <: i <: j <: a in the second summand are wrong in my opinion, and should be 1 <: i < j <: a I tried reporting this to Weisstein a few years ago, but it's still there, so I suppose he disagrees. Cheers, Mike On 01/12/2017 06:49, Roger Hui wrote:
Next exercise: How many primes are < 1e9? You can of course use PrimePi in Mathematica, or p: in J. But suppose those functions are not available. How would you compute that in your favorite language? The erroneous answer 50847478 is cited in various textbooks and even has a name, Bertelsen’s number, memorably described by MathWorld as “an erroneous name erroneously given the erroneous value of π(1e9) = 50847478”. After you solve this, you can compare your answer to *A History of APL in 50 Functions <http://www.jsoftware.com/papers/50/>*, Chapter 46. ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
--- This email has been checked for viruses by Avast antivirus software. https://www.avast.com/antivirus ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
