Category talk:Go-rcu: Difference between revisions
→Source code: Added PrimeCount method.
(→Source code: Added some more functions.) |
(→Source code: Added PrimeCount method.) |
||
Line 2:
<lang go>package rcu
import
"fmt"
"rcu"
)
// Returns the larger of two ints.
Line 111 ⟶ 114:
}
return primes
}
// Sieves for primes up to and including 'n' and returns how many there are.
// Uses an algorithm better suited to counting than the one used in the PrimeSieve method.
func PrimeCount(n int) int {
if n < 2 {
return 0
}
count := 1
k := (n-3)/2 + 1
marked := make([]bool, k) // all false by default
limit := (int(math.Sqrt(float64(n)))-3)/2 + 1
for i := 0; i < limit; i++ {
if !marked[i] {
p := 2*i + 3
s := (p*p - 3) / 2
for j := s; j < k; j += p {
marked[j] = true
}
}
}
for i := 0; i < k; i++ {
if !marked[i] {
count++
}
}
return count
}
| |||