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