Legendre prime counting function: Difference between revisions
Added FreeBASIC
m (→{{header|Wren}}: Changed to Wren S/H) |
(Added FreeBASIC) |
||
Line 1,167:
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|FreeBASIC}}==
<syntaxhighlight lang="vbnet">Function isPrime(n As Uinteger) As Boolean
Dim As Uinteger i
For i = 2 To Sqr(n)
If n Mod i = 0 Then Return False
Next i
Return True
End Function
Dim As Uinteger n, i, j, count
Dim Shared As Ulongint primes(1e8)
n = 1
For i = 0 To 9
count = 0
For j = 2 To n
If isPrime(j) Then
count += 1
primes(count) = j
End If
Next j
Print "10^"; i; " "; count
n *= 10
Next i
Sleep</syntaxhighlight>
=={{header|Go}}==
| |||