A tricky algorithm to calculate the total amount of prime numbers in a certain range was invented by Legendre (Prime-counting function – Wikipedia). The implementation of this algorithm is featured in the free calculator software VincSCalc (since the earliest published versions) which demonstrates its full potential in terms of efficiency. In short terms, the algorithm calculates the amount of prime numbers by calculating the total amount of composite numbers.
The basic idea is quite simple and is part of the Columbus’s egg category: let’s take, for example, the range of numbers from 1 to 210; how many are there composite numbers multiples of 2? Obviously 210/2. And how many multiples of 3? Obviously 210/3. If we sum these two results, we’ll get the total amount of composite numbers of 2 and 3. But how many times I counted twice a multiple composed of 2 or a multiple composed of 3 in the resulting sum? Quite easy! 210/(2*3) that I’m going to subtract the sum. If I repeat the exercise for all pairs of combinations of prime numbers (2-3, 2-5, 2-7, 2-11, 2-13, 3-5, …, 11-13, 13-13), I will get the total amount of composites, among which factors there are individual prime numbers or pairs of prime numbers. But I have not yet considered the composites consisting of three prime numbers as factors. Then let’s go on to add, to the previous result, 210/(2*3*7) and then 210/(2*3*11) and then again 210/(2*3*13) and so on for all the combinations of triplets of prime numbers.
Let’s consider, just for example, the two initial triplets: how many times did I count twice a composite number of the three factors in the initials two combinations used? Again quite easy; 210/(2*3*7*11).
So I’m going to subtract this result to the total amount of composite numbers. And so on for all the combinations of prime numbers taken three by three. Moral of the story? When the count of the composite numbers is carried out by dividing a single prime number, or three prime numbers, or five prime numbers, or any odd combination number prime numbers, the result of the division must be added: this total amount of composite numbers must be subtracted by the result of all divisions in which the combination of the factors equals pairs of prime numbers, quadruple of prime numbers, sextuple of prime numbers, then any even combination of prime numbers.
At the end, to the calculation of “non-prime-numbers” we must add the special number “1” and also to subtract 1 for every prime number considered (in the field 1-210 we will see why the prime numbers considered are in the range from 2 to 13). It only remains to determine how many prime numbers must be included in the calculation of combinations: as in the recent trend of sieves, the square root of 210 (around 14,49) is the limit of the prime numbers to consider; the closest prime number less than 14 is equal to 13. In fact, 13 * 13 = 169 which is inside the given range while 17*17 = 289 which is off the range. But does this mean that all multiples of 17 are all out of the range 1-210? Of course not, but we have already them counted in all composite numbers of 2, as well as in all composite numbers of 3 and all composite numbers of 2*3, etcetera!
Then 17 should not be considered in any combinations of factors as well as 19 and all prime numbers greater than 13. Because, for sure, we can say that all of the composite numbers in the range 1-210 have at least a prime factor which is in the range from 2 to 13. In the field 1-210 does not exist a composite number having a prime factor greater than 13 that has not, at the same time, another prime factor lower or equal to 13. By using, in the calculation, all the combinations of prime factors ranging from 2 to 13, we therefore included in the calculation of all the composite numbers present in the range 1-210.
By the way, the number of primes in the field 1-210 is equal to 46. If you want to understand, with colorful graphics, how the algorithm works, you can download a .pdf sheet from the following link …
http://www.vincs.it/upfiles/HowManyPrimesCalculatingComposites%20-%2020160709%20-%20EN.pdf
If you want to accurately calculate the number of primes in any range of numbers from 1 to 10,000,000 (ten million) you can download the free to use calculator VincSCalc and use the πc functions (pi calculations), at bottom right of the keyboard, after having choose by menu CalcSettings / DataType / BigInt …
You can download VincSCalc from http://www.vincs.it/VincSCalc
VincSmath 