12345678910111213141516171819202122232425262728293031323334 |
- #!/usr/bin/ruby
- # The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.
- # Find the sum of all the primes below two million.
- # https://projecteuler.net/problem=10
- # Runtime: 1.138s
- func sum_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, faulhaber(k,1)) }...)
- 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} -= p*(S{idiv(v,p)} - sp)
- }
- }
- return S{n}-1
- }
- say sum_of_primes(2e6)
|