12345678910111213141516171819202122232425262728293031323334353637 |
- #!/usr/bin/ruby
- # Sublinear algorithm for counting the number of primes <= n.
- # Based on algorithm from:
- # https://math.stackexchange.com/questions/1378286/find-the-sum-of-all-primes-smaller-than-a-big-number
- func count_of_primes(n) {
- return 0 if (n <= 1)
- var r = n.isqrt
- var V = (1..r -> map {|k| idiv(n,k) })
- V << range(V.last-1, 1, -1).to_a...
- var S = Hash(V.map{|k| (k, k) }...)
- for p in (2..r) {
- S{p} > S{p-1} || next
- var sp = S{p-1}
- var p2 = p*p
- V.each {|v|
- break if (v < p2)
- S{v} -= (S{idiv(v,p)} - sp)
- }
- }
- return S{n}-1
- }
- assert_eq(
- 30.of { count_of_primes(_) }
- 30.of { .pi }
- )
- say count_of_primes(1e6) #=> 78498
|