107 lines
2.8 KiB
Go
107 lines
2.8 KiB
Go
package main
|
|
|
|
import (
|
|
"fmt"
|
|
"math"
|
|
"time"
|
|
)
|
|
|
|
var masks = [8]uint8{1, 2, 4, 8, 16, 32, 64, 128}
|
|
|
|
func half(n int) int { return (n - 1) >> 1 }
|
|
|
|
func divide(nm, d uint64) int { return int(float64(nm) / float64(d)) }
|
|
|
|
func countPrimes(n uint64) int64 {
|
|
if n < 9 {
|
|
if n < 2 {
|
|
return 0
|
|
} else {
|
|
return (int64(n) + 1) / 2
|
|
}
|
|
}
|
|
rtlmt := int(math.Sqrt(float64(n)))
|
|
mxndx := (rtlmt - 1) / 2
|
|
arrlen := mxndx + 1
|
|
smalls := make([]uint32, arrlen)
|
|
roughs := make([]uint32, arrlen)
|
|
larges := make([]int64, arrlen)
|
|
for i := uint32(0); i < uint32(arrlen); i++ {
|
|
smalls[i] = i
|
|
roughs[i] = i + i + 1
|
|
larges[i] = int64((n/uint64(i+i+1) - 1) / 2)
|
|
}
|
|
cullbuflen := (mxndx + 8) / 8
|
|
cullbuf := make([]uint8, cullbuflen)
|
|
nbps := 0
|
|
rilmt := arrlen
|
|
for i := 1; ; i++ {
|
|
sqri := (i + i) * (i + 1)
|
|
if sqri > mxndx {
|
|
break
|
|
}
|
|
if (cullbuf[i>>3] & masks[i&7]) != 0 {
|
|
continue
|
|
}
|
|
cullbuf[i>>3] |= masks[i&7]
|
|
bp := i + i + 1
|
|
for c := sqri; c < arrlen; c += bp {
|
|
cullbuf[c>>3] |= masks[c&7]
|
|
}
|
|
nri := 0
|
|
for ori := 0; ori < rilmt; ori++ {
|
|
r := int(roughs[ori])
|
|
rci := r >> 1
|
|
if (cullbuf[rci>>3] & masks[rci&7]) != 0 {
|
|
continue
|
|
}
|
|
d := r * bp
|
|
t := int64(0)
|
|
if d <= rtlmt {
|
|
t = larges[int(smalls[d>>1])-nbps]
|
|
} else {
|
|
t = int64(smalls[half(divide(n, uint64(d)))])
|
|
}
|
|
larges[nri] = larges[ori] - t + int64(nbps)
|
|
roughs[nri] = uint32(r)
|
|
nri++
|
|
}
|
|
si := mxndx
|
|
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 - uint32(nbps))
|
|
}
|
|
}
|
|
rilmt = nri
|
|
nbps++
|
|
}
|
|
ans := larges[0] + int64(((rilmt + 2*(nbps-1)) * (rilmt - 1) / 2))
|
|
for ri := 1; ri < rilmt; ri++ {
|
|
ans -= larges[ri]
|
|
}
|
|
for ri := 1; ; ri++ {
|
|
p := uint64(roughs[ri])
|
|
m := n / p
|
|
ei := int(smalls[half(int(m/p))]) - nbps
|
|
if ei <= ri {
|
|
break
|
|
}
|
|
ans -= int64((ei - ri) * (nbps + ri - 1))
|
|
for sri := ri + 1; sri < ei+1; sri++ {
|
|
ans += int64(smalls[half(divide(m, uint64(roughs[sri])))])
|
|
}
|
|
}
|
|
return ans + 1
|
|
}
|
|
|
|
func main() {
|
|
start := time.Now()
|
|
for i, n := uint64(0), uint64(1); i <= 9; i, n = i+1, n*10 {
|
|
fmt.Printf("10^%d %d\n", i, countPrimes(n))
|
|
}
|
|
elapsed := time.Since(start).Microseconds()
|
|
fmt.Printf("\nTook %d microseconds\n", elapsed)
|
|
}
|