Legendre prime counting function: Difference between revisions

<br>

<br>

 

=={{header|C}}==

 

int64_t countPrimes(uint64_t n) {

uint64_t rtlmt = (uint64_t)sqrt((double)n);

int64_t mxndx = (int64_t)((rtlmt - 1) / 2);

 

The above function enjoys quite a large gain in speed of about a further ten times over the immediately preceding version due to not using recursion at all and the greatly reduced computational complexity of O(n**(3/4)/((log n)**2)) instead of the almost-linear-for-large-counting-ranges O(n/((log n)**2)) for the previous two versions, although the previous two versions differ in performance by a constant factor due to the overheads of recursion and division. This version of prime counting function might be considered to be reasonably useful for counting primes up to a 1e16 in almost two minutes as long as the computer used has the required free memory of about 800 Megabytes. This Crystal version is about twice as slow as the Nim version from which it was translated because Nim's default GCC back-end is better at optimization (at least for this algorithm) than the LLVM back-end used by Crystal and also there is more numeric calculation checking such as numeric overflow used in Crystal that can't be turned off. At that, this version is about the same speed as when translated to Rust, which also uses a LLVM back-end.

 

=={{header|Erlang}}==

 

The above function enjoys quite a large gain in speed of about a further ten times over the immediately preceding version (although one can't see that gain for these trivial ranges as it is buried in the constant overheads) due to not using recursion at all and the greatly reduced computational complexity of O(n**(3/4)/((log n)**2)) instead of the almost-linear-for-large-counting-ranges O(n/((log n)**2)) for the previous two versions, although the previous two versions differ in performance by a constant factor due to the overheads of recursion and division; for instance, this version can calculate the number of primes to 1e11 in about a hundred milliseconds. This version of prime counting function might be considered to be reasonably useful for counting primes up to a 1e16 in about a hundred seconds as long as the computer used has the required free memory of about 800 Megabytes. This F# version is about twice as slow as the Nim version from which it was translated due to the benefits of native code compilation and more optimizations for Nim rather than JIT compilation for F#. At that, this version is about the same speed as when translated to Rust and Crystal once the range is increased where constant overheads aren't a factor, which both use native code compilers.

 

=={{header|Go}}==

 

func countPrimes(n uint64) int64 {

if n < 2 {

return 0

} else {

}

}

10^9 50847534

0.003234 seconds (421 allocations: 14.547 KiB)

</pre>

 

5761455

50847534</pre>

 

=={{header|Nim}}==

for i in 0..9:

echo "π(10^$1) = $2".format(i, π(n))

 

{{out}}

 

As counting range is increased above these trivial ranges, a better algorithm such as that of LMO will likely perform much better than this and use much less memory (to proportional to the cube root of the range), although at the cost of greater code complexity and more lines of code (about 500 LOC). The trade-off between algorithms of the Legendre type and those of the Meissel type is that the latter decreases the time complexity but at the cost of more time spent sieving; modern follow-on work to LMO produces algorithms which are able to tune the balance between Legendre-type and Meissel-type algorithm in trading off the execution time costs between the different parts of the given algorithm for the best in performance, with the latest in Kim Walisch's tuning of Xavier Gourdon's work being about five to ten times faster than LMO (plus includes multi-threading abilities).

 

=={{header|Perl}}==

</pre>

<small>(It is about 4 times slower under pwa/p2js so output is limited to 10^8, unless you like staring at a blank screen for 52s)</small>

 

=={{header|Picat}}==

</pre>

 

=={{header|Sidef}}==

<syntaxhighlight lang="ruby">func legendre_phi(x, a) is cached {

[direct_array_access]

fn count_primes_to(n u64) i64 {

rtlmt := u64(sqrt(f64(n)))

mxndx := i64((rtlmt - 1) / 2)

 

To sieve a billion numbers and then count the primes up to 10^k would take about 53 seconds in Wren so, as expected, the Legendre method represents a considerable speed up.

 

var pi = Fn.new { |n|

 

The memoized version requires a cache of around 6.5 million map entries, which at 8 bytes each (all numbers are 64 bit floats in Wren) for both the key and the value, equates in round figures to memory usage of 104 MB on top of that needed for the prime sieve. The following version strips out memoization and, whilst somewhat slower at 5.4 seconds, may be preferred in a constrained memory environment.

 

var pi = Fn.new { |n|

{{trans|Vlang}}

This non-memoized, non-recursive version is far quicker than the first two versions, running in about 114 milliseconds. Nowhere near as quick as V, of course, but acceptable for Wren which is interpreted and only has one built-in numeric type, a 64 bit float.

 

var masks = [1, 2, 4, 8, 16, 32, 64, 128]

 

var countPrimes = Fn.new { |n|

var rtlmt = n.sqrt.floor

var mxndx = Int.quo(rtlmt - 1, 2)