With positive ints or longs--where pj is the jth prime:
P(x,n) = x - 1 - sum for j=1 to n of {P(x/pj,j-1) - (j-1)}
The P(x,n) function will count primes up to and including x, if n equals the count of primes up to sqrt(x), and if as you iterate you never let n be greater than the count of primes up to and including sqrt(x), if the function receives an n greater than that value it just needs to reset it to that count.
That is the fastest algorithm for counting primes for its size.
For say, the count of primes up to 100, if you tried P(100,10), the algorithm would reset n to n=4, so you'd have P(100,4), because there are 4 primes--2, 3, 5 and 7--up to sqrt(100).
Notice with just those 4 primes you count all primes up to 100.
P(100,4) = 100 - 1 - (P(50, 0) - 0) - (P(33,1) - 1) - (P(20,2) - 2) - (P(14,3) - 3)
Except P(14,3) needs a correction because the 3rd prime is 5 which squares to 25, so that is going too high as it's bigger than 14 and has to be reset to P(14,2). Then I have:
P(100,4) = 100 - 1 - 49 - 16 - 6 - 3 = 25
Those numbers are explained simply enough: there are 49 even composites, 16 odd composites with 3 as a factor, 6 composites with 5 as a factor but no smaller prime as a factor. And 3 that have 7 as a factor with no smaller prime, and I'll give those as it's just three numbers so easy to do and they are of course: 49, 77 and 91.
And you subtract 1 for 1 itself, where the principle is easy enough--subtract composites and 1 to get the count of primes.
Another example is P(10,2) = 10 - 1 - (P(5,0) - 0) - (P(3,1) - 1) = 10 - 1 - 4 - 1 = 4
Where of course the 4 primes are 2, 3, 5 and 7.
There are 4 even composites--4, 6, 8, 10--which are being counted by P(5,0) and one composite divisible by 3, which is NOT even, which is 9, and that count is given by P(3,1) - 1 = 1.
The algorithm is fairly easy to program.
So you need a list of primes up to sqrt(x), so the hardest thing is how you generate that list of primes, which is usually done using the Sieve of Eratosthenes, even for the currently established fastest prime counting algorithms known! But for something quick you can just enter a small list.
For example the first 10 primes are:
2, 3, 5, 7, 11, 13, 17, 19, 23, 29
With that list using the algorithm you can count primes up to 29*29 = 841.
The P function also has to check to see that n is not greater than count of primes up to, and including sqrt(x), where a simple implementation is just brute force, find floor(sqrt(x)) and count primes, for instance for 840, floor(sqrt(840)) = 28, and you can just count up to see that n = 9, as 23 is the last prime less than or equal to 28.
Notice at 529 = 23*23, you'd still have n = 9, as you go up to and including sqrt(x).
You can actually get clever here as n tries to go greater at a very specific place as you iterate, so you don't actually have to check the square root at each iteration, but am just showing the simplest route to implementation.
To see a recent rather long-winded explanation of how the algorithm is derived and to understand why it works you can click here. No advanced math in the derivation, as you just need to know what a prime is and what division is, as well as some basic algebra to follow it.
The basic idea of counting composites and subtracting 1 to count primes is centuries old.
What's new with my prime counting function is a slight tweak.
I just did one little extra thing that no one did before over those centuries, which makes it more concise, easier to explain, understand and, importantly, implement.
If you're mathematically adventurous you can have it call itself to remove needing to give it a list of any primes, but then it's a lot slower. Run timing tests if you wish to see how much slower. But that is just a lot more recursion, and you can do things to speed it back up, if you're bored.
I've had it for over ten years, so I no longer play with it. Had all my fun with it years ago.
James Harris
No comments:
Post a Comment