Counting Primes¶
AUTHORS:
R. Andrew Ohana (2009): initial version of efficient prime_pi
William Stein (2009): fix plot method
R. Andrew Ohana (2011): complete rewrite, ~5x speedup
EXAMPLES:
sage: z = sage.functions.prime_pi.PrimePi()
sage: loads(dumps(z))
prime_pi
sage: loads(dumps(z)) == z
True
- class sage.functions.prime_pi.PrimePi¶
Bases:
sage.symbolic.function.BuiltinFunction
The prime counting function, which counts the number of primes less than or equal to a given value.
INPUT:
x
- a real numberprime_bound
- (default 0) a real number < 2^32,prime_pi
will make sure to use all the primes up toprime_bound
(although, possibly more) in computingprime_pi
, this can potentially speedup the time of computation, at a cost to memory usage.
OUTPUT:
integer – the number of primes \(\leq\)
x
EXAMPLES:
These examples test common inputs:
sage: prime_pi(7) 4 sage: prime_pi(100) 25 sage: prime_pi(1000) 168 sage: prime_pi(100000) 9592 sage: prime_pi(500509) 41581
These examples test a variety of odd inputs:
sage: prime_pi(3.5) 2 sage: prime_pi(sqrt(2357)) 15 sage: prime_pi(mod(30957, 9750979)) Traceback (most recent call last): ... TypeError: cannot coerce arguments: positive characteristic not allowed in symbolic computations
We test non-trivial
prime_bound
values:sage: prime_pi(100000, 10000) 9592 sage: prime_pi(500509, 50051) 41581
The following test is to verify that trac ticket #4670 has been essentially resolved:
sage: prime_pi(10^10) 455052511
The
prime_pi
function also has a special plotting method, so it plots quickly and perfectly as a step function:sage: P = plot(prime_pi, 50, 100)
Note
This uses a recursive implementation, using the optimizations described in [Oha2011].
AUTHOR:
R. Andrew Ohana (2011)
- plot(xmin=0, xmax=100, vertical_lines=True, **kwds)¶
Draw a plot of the prime counting function from
xmin
toxmax
. All additional arguments are passed on to the line command.WARNING: we draw the plot of
prime_pi
as a stairstep function with explicitly drawn vertical lines where the function jumps. Technically there should not be any vertical lines, but they make the graph look much better, so we include them. Use the optionvertical_lines=False
to turn these off.EXAMPLES:
sage: plot(prime_pi, 1, 100) Graphics object consisting of 1 graphics primitive sage: prime_pi.plot(-2, sqrt(2501), thickness=2, vertical_lines=False) Graphics object consisting of 16 graphics primitives
- sage.functions.prime_pi.legendre_phi(x, a)¶
Legendre’s formula, also known as the partial sieve function, is a useful combinatorial function for computing the prime counting function (the
prime_pi
method in Sage). It counts the number of positive integers \(\leq\)x
that are not divisible by the firsta
primes.INPUT:
x
– a real numbera
– a non-negative integer
OUTPUT:
integer – the number of positive integers \(\leq\)
x
that are not divisible by the firsta
primesEXAMPLES:
sage: legendre_phi(100, 0) 100 sage: legendre_phi(29375, 1) 14688 sage: legendre_phi(91753, 5973) 2893 sage: legendre_phi(7.5, 2) 3 sage: legendre_phi(str(-2^100), 92372) 0 sage: legendre_phi(4215701455, 6450023226) 1
Note
This uses a recursive implementation, using the optimizations described in [Oha2011].
AUTHOR:
R. Andrew Ohana (2011)
- sage.functions.prime_pi.partial_sieve_function(x, a)¶
Legendre’s formula, also known as the partial sieve function, is a useful combinatorial function for computing the prime counting function (the
prime_pi
method in Sage). It counts the number of positive integers \(\leq\)x
that are not divisible by the firsta
primes.INPUT:
x
– a real numbera
– a non-negative integer
OUTPUT:
integer – the number of positive integers \(\leq\)
x
that are not divisible by the firsta
primesEXAMPLES:
sage: legendre_phi(100, 0) 100 sage: legendre_phi(29375, 1) 14688 sage: legendre_phi(91753, 5973) 2893 sage: legendre_phi(7.5, 2) 3 sage: legendre_phi(str(-2^100), 92372) 0 sage: legendre_phi(4215701455, 6450023226) 1
Note
This uses a recursive implementation, using the optimizations described in [Oha2011].
AUTHOR:
R. Andrew Ohana (2011)