Legendre prime counting function: Difference between revisions
→{{header|Vlang}}: correction to increase precision to extend range...
(Added C) |
GordonBGood (talk | contribs) (→{{header|Vlang}}: correction to increase precision to extend range...) |
||
Line 3,099:
[inline]
fn half(n
[inline] // floating point divide faster than integer divide!
fn divide(nm u64, d u64)
[direct_array_access]
fn count_primes_to(n u64) i64 {
if n < u64(3) { return if n < i64(2) { i64(0) } else { i64(1) } }
rtlmt :=
mxndx := i64((rtlmt - 1) / 2)
arrlen := int(mxndx + 1)
mut smalls := []u32{ len: arrlen, cap: arrlen, init: u32(it) }
mut roughs := []u32{ len: arrlen, cap: arrlen, init: u32(it + it + 1) }
mut larges := []i64{ len: arrlen, cap: arrlen,
init: i64(((n / u64(it + it + 1) - 1) / 2)) }
cullbuflen := int((mxndx + 8) / 8)
mut cullbuf := []u8{len: cullbuflen, cap: cullbuflen, init: u8(0)}
mut nbps := i64(0) // do partial sieving for each odd base prime to quad root...
mut rilmt := arrlen // number of roughs start with full size!
for i := i64(1); ; i++ { // start with 3; breaks when partial sieving done...
sqri := (i + i) * (i + 1)
if sqri > mxndx { break } // breaks here!
if (cullbuf[i >>> 3] & masks[i & 7]) != u8(0) { continue } // not prime!
cullbuf[i >>> 3] |= masks[i & 7] // cull bp rep!
bp := u64(i + i + 1) // partial sieve by bp...
for c := sqri; c < arrlen; c += i64(bp) { cullbuf[c >>> 3] |= masks[c & 7] }
mut nri := 0 // transfer from `ori` to `nri` indexes:
for ori in 0 .. rilmt { // update `roughs` and `larges` for partial sieve...
if (cullbuf[
d :=
larges[nri] = larges[ori] -
(if d <= rtlmt { larges[
else { i64(smalls[half(divide(n,
+
roughs[nri] =
nri++ // advance output `roughs` index!
}
Line 3,142:
mut si := mxndx // update `smalls` for partial sieve...
for pm := ((rtlmt / bp) - 1) | 1; pm >= bp; pm -= 2 {
c := smalls[pm >>> 1]
e := (pm * bp) >>> 1
for ; si >= e; si-- { smalls[si] -= (c - u32(nbps)) }
}
Line 3,159:
p := u64(roughs[ri])
m := n / p
ei := int(smalls[half(
if ei <= ri { break } // break out when only multiple equal to `p`
ans -= i64((ei - ri) * (nbps + ri - 1)) // adjust for over addition below!
Line 3,189:
This took 2 milliseconds.</pre>
The above code is about as fast as the same algorithm in the fastest of languages such as C/C++/Nim due to the greatly reduced computational complexity of O(n**(3/4)/((log n)**2)); it can compute the number of primes to 1e11 in about 22 milliseconds on the same machine as shown where it is run on an Intel i5-6500 (3.6 GHz single-thread boosted). The above code can
=={{header|Wren}}==
| |||