(*********************************************************************

	Copyright 1989 by Roman E. Maeder
	
	Adapted from
	Roman E. Maeder: Programming in Mathematica, Addison-Wesley, 1989.

	Permission is hereby granted to make copies of this file for
	any purpose other than direct profit, or as part of a
	commercial product, provided this copyright notice is left
	intact.  Sale, other than for the cost of media, is prohibited.
	
	Permission is hereby granted to reproduce part or all of
	this file, provided that the source is acknowledged.

 *********************************************************************)


PrimePi::usage = "PrimePi[x] returns the number of primes <= x."

Attributes[PrimePi] = {Listable}

Begin["`Private`"]

PrimePi[x_] := 0 /; x < 2

PrimePi[x_] :=
	Block[{`li, `n0, `n1, `m, `nx = N[x]},
		li = LogIntegral[nx];
		n0 = Floor[li - LogIntegral[Sqrt[nx]]];
		n1 = Ceiling[li];
		While[ n1-n0 > 1,
			m = Floor[(n0+n1)/2];                 (* midpoint *)
			If[ Prime[m] <= nx, n0 = m, n1 = m ]
		];
		n0
	] /; x >= 2

End[]
Null
