Counting tops

Let $\pi(x)$ be the variety of tops not more than $x$.

Wikipedia article claims that $\pi(10^{23}) = 1,925,320,391,606,803,968,923$.

The inquiry is just how to compute $\pi(x)$ for huge $x$ in a practical time? What algorithms do exist for that?

0
2019-05-07 13:38:59
Source Share
Answers: 3

You can make use of inclusion exclusion principle to get an increase over the Eratosthenes sieve

0
2019-05-09 09:05:20
Source

The most reliable prime checking algorithms presently recognized are all basically optimizations of the method created by Meissel in 1870, as an example see the conversation below http://primes.utm.edu/howmany.shtml

0
2019-05-09 09:04:06
Source

The Sieve of Atkin is just one of the fastest algorithm made use of to compute $pi(x)$. The Wikipedia web page claims that its intricacy is O (N/ log log N).

(edit)

I located a distributed computation project which had the ability to compute $pi(4\times 10^{22})$, possibly maybe valuable.

0
2019-05-09 08:40:29
Source