Summation of primes: Difference between revisions
→{{header|Sidef}}: added a sublinear version
(Added Sidef) |
(→{{header|Sidef}}: added a sublinear version) |
||
Line 620:
<lang ruby>say sum_primes(2e6) #=> 142913828922</lang>
Linear algorithm:
<lang ruby>func sum_primes(limit) {
var sum = 0
Line 630:
say sum_primes(2e6)</lang>
Sublinear algorithm:
<lang ruby>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, polygonal(k,3)) }...)
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)</lang>
{{out}}
<pre>
| |||