Legendre prime counting function: Difference between revisions
m
→Non-Memoized Versions: Nim - tuned comments on partial sieving implementation...
GordonBGood (talk | contribs) m (Further clarification of comments on the Legendre prime counting task...) |
GordonBGood (talk | contribs) m (→Non-Memoized Versions: Nim - tuned comments on partial sieving implementation...) |
||
Line 1,161:
The reason that this algorithm can reduce the number of operations as compared to the "standard" recursive Legendre algorithm in that the product of some combinations of multiple primes is compensated in one operation rather than many "branching"/recursive operations as in the recursive or semi-recursive algorithms.
One might question the validity of this "partial sieving" optimization considering the task explanation, but the Legendre prime counting function was likely never used practically at the time it was invented other than for trivial examples showing that it worked as mentioned above since there were no electronic computers; the follow-on work by Meissel was used by him to hand calculate the number of primes to a billion (1e9) over the course of some number of years in about 1870, and he
A Nim implementation of the above described algorithm is as follows:
|