Counting Primes
AUTHORS:
EXAMPLES:
sage: z = sage.functions.prime_pi.PrimePi()
sage: loads(dumps(z))
prime_pi
sage: loads(dumps(z)) == z
True
Bases: sage.symbolic.function.BuiltinFunction
The prime counting function, which counts the number of primes less than or equal to a given value.
INPUT:
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.00000000000000
sage: prime_pi(sqrt(2357))
15
sage: prime_pi(mod(30957, 9750979))
3337
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 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)
NOTES:
Uses a recursive implementation, using the optimizations described in [RAO2011].
REFERENCES:
[RAO2011] | (1, 2, 3) R.A. Ohana. On Prime Counting in Abelian Number Fields. http://wstein.org/home/ohanar/papers/abelian_prime_counting/main.pdf. |
AUTHOR:
Draw a plot of the prime counting function from xmin to xmax. 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 option vertical_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
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 first a primes.
INPUT:
OUTPUT:
integer – the number of positive integers \(\leq\) x that are not divisible by the first a primes
EXAMPLES:
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
NOTES:
Uses a recursive implementation, using the optimizations described in [RAO2011].
AUTHOR:
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 first a primes.
INPUT:
OUTPUT:
integer – the number of positive integers \(\leq\) x that are not divisible by the first a primes
EXAMPLES:
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
NOTES:
Uses a recursive implementation, using the optimizations described in [RAO2011].
AUTHOR: