Report as inappropriate.
So this was my experiment once when influenced to play with primes a couple hours from a math class.
To the left is a graph of a particular distribution of the first 1900 primes.
Stores a growing list of known primes.
Can check if a given integer is a prime.
Can retrieve the i'th prime.
Can determine the result of the pi function (prime-counting function) of a given double.
Updates list of primes as needed for queries.
Checking a candidate for the next prime (to be added to growing list) has running time: n (the size of the growing list of known primes)
Determining an integer is prime has running time: lg n (binary search) *
Evaluating pi has running time: lg n (binary search) *
*not including running time of finding next primes when list is insufficient.
Want to leave a comment? You must first log in.
No votes yet.