Legendre prime counting function: Difference between revisions
no edit summary
No edit summary |
No edit summary |
||
Line 11:
π(n) = φ(x, a) + a - 1, where a = π(√n)
The Legendre formula still requires the use of a sieve to enumerate primes; however it's only required to sieve up to the √n, and for counting primes, the Legendre method is much faster than sieving up to n.
;Task:
Calculate π(n) for values up to 1 billion. Show π(n) for n = 1, 10, 100, ... 10<sup>9</sup>.
For this task, you may refer to a prime number sieve (such as the Sieve of Eratosthenes or the extensible sieve) in an external library to enumerate the primes required by the formula.
=={{header|CoffeeScript}}==
Line 117 ⟶ 119:
main(_) ->
put(primes, array:from_list(primality:sieve(
ets:new(memphi, [set, named_table, protected]),
output(0, 9).
| |||