Summation of primes: Difference between revisions
(→{{header|Sidef}}: added a sublinear version) |
Thundergnat (talk | contribs) m (syntax highlighting fixup automation) |
||
Line 9: | Line 9: | ||
=={{header|ALGOL 68}}== |
=={{header|ALGOL 68}}== |
||
{{libheader|ALGOL 68-primes}} |
{{libheader|ALGOL 68-primes}} |
||
< |
<syntaxhighlight lang="algol68">BEGIN # sum primes up to 2 000 000 # |
||
PR read "primes.incl.a68" PR |
PR read "primes.incl.a68" PR |
||
# return s space-separated into groups of 3 digits # |
# return s space-separated into groups of 3 digits # |
||
Line 33: | Line 33: | ||
OD; |
OD; |
||
print( ( space separate( whole( sum, 0 ) ), newline ) ) |
print( ( space separate( whole( sum, 0 ) ), newline ) ) |
||
END</ |
END</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 43: | Line 43: | ||
This isn't something that's likely to needed more than once — if at all — so you'd probably just throw together code like the following. The result's interesting in that although it's way outside AppleScript's integer range, its class is returned as integer in macOS 10.14 (Mojave)! |
This isn't something that's likely to needed more than once — if at all — so you'd probably just throw together code like the following. The result's interesting in that although it's way outside AppleScript's integer range, its class is returned as integer in macOS 10.14 (Mojave)! |
||
< |
<syntaxhighlight lang="applescript">on isPrime(n) |
||
if ((n < 4) or (n is 5)) then return (n > 1) |
if ((n < 4) or (n is 5)) then return (n > 1) |
||
if ((n mod 2 = 0) or (n mod 3 = 0) or (n mod 5 = 0)) then return false |
if ((n mod 2 = 0) or (n mod 3 = 0) or (n mod 5 = 0)) then return false |
||
Line 67: | Line 67: | ||
end sumPrimes |
end sumPrimes |
||
sumPrimes below 2000000</ |
sumPrimes below 2000000</syntaxhighlight> |
||
{{output}} |
{{output}} |
||
<lang |
<syntaxhighlight lang="applescript">142913828922</syntaxhighlight> |
||
The result can be obtained in 4 seconds rather than 14 if the summing's instead combined with an Eratosthenean sieve: |
The result can be obtained in 4 seconds rather than 14 if the summing's instead combined with an Eratosthenean sieve: |
||
< |
<syntaxhighlight lang="applescript">on sumPrimes below this |
||
set limit to this - 1 |
set limit to this - 1 |
||
-- Is the limit 2 or lower? |
-- Is the limit 2 or lower? |
||
Line 124: | Line 124: | ||
end sumPrimes |
end sumPrimes |
||
sumPrimes below 2000000</ |
sumPrimes below 2000000</syntaxhighlight> |
||
=={{header|AWK}}== |
=={{header|AWK}}== |
||
<syntaxhighlight lang="awk"> |
|||
<lang AWK> |
|||
# syntax: GAWK -f SUMMATION_OF_PRIMES.AWK |
# syntax: GAWK -f SUMMATION_OF_PRIMES.AWK |
||
BEGIN { |
BEGIN { |
||
Line 161: | Line 161: | ||
return(1) |
return(1) |
||
} |
} |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 170: | Line 170: | ||
=={{header|BASIC}}== |
=={{header|BASIC}}== |
||
==={{header|FreeBASIC}}=== |
==={{header|FreeBASIC}}=== |
||
< |
<syntaxhighlight lang="freebasic">#include "isprime.bas" |
||
dim as integer sum = 2, i, n=1 |
dim as integer sum = 2, i, n=1 |
||
Line 180: | Line 180: | ||
next i |
next i |
||
print sum</ |
print sum</syntaxhighlight> |
||
{{out}}<pre>142913828922</pre> |
{{out}}<pre>142913828922</pre> |
||
==={{header|GW-BASIC}}=== |
==={{header|GW-BASIC}}=== |
||
< |
<syntaxhighlight lang="gwbasic">10 S# = 2 |
||
20 FOR P = 3 TO 1999999! STEP 2 |
20 FOR P = 3 TO 1999999! STEP 2 |
||
30 GOSUB 80 |
30 GOSUB 80 |
||
Line 199: | Line 199: | ||
140 Q = 1 |
140 Q = 1 |
||
150 RETURN |
150 RETURN |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}}<pre>142913828922</pre> |
{{out}}<pre>142913828922</pre> |
||
=={{header|C}}== |
=={{header|C}}== |
||
< |
<syntaxhighlight lang="c">#include<stdio.h> |
||
#include<stdlib.h> |
#include<stdlib.h> |
||
Line 224: | Line 224: | ||
printf( "%ld\n", s ); |
printf( "%ld\n", s ); |
||
return 0; |
return 0; |
||
}</ |
}</syntaxhighlight> |
||
{{out}}<pre>142913828922</pre> |
{{out}}<pre>142913828922</pre> |
||
=={{header|CLU}}== |
=={{header|CLU}}== |
||
< |
<syntaxhighlight lang="clu">isqrt = proc (s: int) returns (int) |
||
x0: int := s/2 |
x0: int := s/2 |
||
if x0=0 then |
if x0=0 then |
||
Line 263: | Line 263: | ||
start_up = proc () |
start_up = proc () |
||
stream$putl(stream$primary_output(), int$unparse(sum_primes_to(2000000))) |
stream$putl(stream$primary_output(), int$unparse(sum_primes_to(2000000))) |
||
end start_up </ |
end start_up </syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>142913828922</pre> |
<pre>142913828922</pre> |
||
=={{header|Crystal}}== |
=={{header|Crystal}}== |
||
< |
<syntaxhighlight lang="ruby">def prime?(n) # P3 Prime Generator primality test |
||
return false unless (n | 1 == 3 if n < 5) || (n % 6) | 4 == 5 |
return false unless (n | 1 == 3 if n < 5) || (n % 6) | 4 == 5 |
||
sqrt = Math.isqrt(n) |
sqrt = Math.isqrt(n) |
||
Line 285: | Line 285: | ||
puts "The sum of all primes below 2 million is #{(0i64..2000000i64).sum { |n| prime?(n) ? n : 0u64 }}" |
puts "The sum of all primes below 2 million is #{(0i64..2000000i64).sum { |n| prime?(n) ? n : 0u64 }}" |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre>The sum of all primes below 2 million is 142913828923. |
<pre>The sum of all primes below 2 million is 142913828923. |
||
Line 292: | Line 292: | ||
=={{header|F_Sharp|F#}}== |
=={{header|F_Sharp|F#}}== |
||
This task uses [http://www.rosettacode.org/wiki/Extensible_prime_generator#The_functions Extensible Prime Generator (F#)] |
This task uses [http://www.rosettacode.org/wiki/Extensible_prime_generator#The_functions Extensible Prime Generator (F#)] |
||
< |
<syntaxhighlight lang="fsharp"> |
||
// Summation of primes. Nigel Galloway: November 9th., 2021 |
// Summation of primes. Nigel Galloway: November 9th., 2021 |
||
printfn $"%d{primes64()|>Seq.takeWhile((>)2000000L)|>Seq.sum}" |
printfn $"%d{primes64()|>Seq.takeWhile((>)2000000L)|>Seq.sum}" |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 302: | Line 302: | ||
=={{header|Factor}}== |
=={{header|Factor}}== |
||
< |
<syntaxhighlight lang="factor">USING: math.primes prettyprint sequences ; |
||
2,000,000 primes-upto sum .</ |
2,000,000 primes-upto sum .</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 311: | Line 311: | ||
=={{header|Fermat}}== |
=={{header|Fermat}}== |
||
< |
<syntaxhighlight lang="fermat">s:=2; |
||
for p=3 to 1999999 by 2 do if Isprime(p) then s:=s+p fi od; |
for p=3 to 1999999 by 2 do if Isprime(p) then s:=s+p fi od; |
||
!!s;</ |
!!s;</syntaxhighlight> |
||
{{out}}<pre>142913828922</pre> |
{{out}}<pre>142913828922</pre> |
||
=={{header|Go}}== |
=={{header|Go}}== |
||
{{libheader|Go-rcu}} |
{{libheader|Go-rcu}} |
||
< |
<syntaxhighlight lang="go">package main |
||
import ( |
import ( |
||
Line 331: | Line 331: | ||
} |
} |
||
fmt.Printf("The sum of all primes below 2 million is %s.\n", rcu.Commatize(sum)) |
fmt.Printf("The sum of all primes below 2 million is %s.\n", rcu.Commatize(sum)) |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 340: | Line 340: | ||
=={{header|Haskell}}== |
=={{header|Haskell}}== |
||
< |
<syntaxhighlight lang="haskell">import Data.Numbers.Primes (primes) |
||
sumOfPrimesBelow :: Integral a => a -> a |
sumOfPrimesBelow :: Integral a => a -> a |
||
Line 347: | Line 347: | ||
main :: IO () |
main :: IO () |
||
main = print $ sumOfPrimesBelow 2000000</ |
main = print $ sumOfPrimesBelow 2000000</syntaxhighlight> |
||
{{Out}} |
{{Out}} |
||
<pre>142913828922</pre> |
<pre>142913828922</pre> |
||
Line 357: | Line 357: | ||
See [[Erd%C5%91s-primes#jq]] for a suitable definition of `is_prime/1` as used here. |
See [[Erd%C5%91s-primes#jq]] for a suitable definition of `is_prime/1` as used here. |
||
< |
<syntaxhighlight lang="jq">def sum(s): reduce s as $x (0; .+$x); |
||
sum(2, range(3 ; 2E6; 2) | select(is_prime))</ |
sum(2, range(3 ; 2E6; 2) | select(is_prime))</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 366: | Line 366: | ||
=={{header|Julia}}== |
=={{header|Julia}}== |
||
< |
<syntaxhighlight lang="julia">using Primes |
||
@show sum(primes(2_000_000)) # sum(primes(2000000)) = 142913828922 |
@show sum(primes(2_000_000)) # sum(primes(2000000)) = 142913828922 |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header|Mathematica}} / {{header|Wolfram Language}}== |
=={{header|Mathematica}} / {{header|Wolfram Language}}== |
||
< |
<syntaxhighlight lang="mathematica">Total[Most@NestWhileList[NextPrime, 2, # < 2000000 &]]</syntaxhighlight> |
||
{{out}}<pre> |
{{out}}<pre> |
||
Line 378: | Line 378: | ||
=={{header|PARI/GP}}== |
=={{header|PARI/GP}}== |
||
< |
<syntaxhighlight lang="parigp"> |
||
s=2; p=3 |
s=2; p=3 |
||
while(p<2000000,if(isprime(p),s=s+p);p=p+2) |
while(p<2000000,if(isprime(p),s=s+p);p=p+2) |
||
print(s) |
print(s) |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}}<pre> |
{{out}}<pre> |
||
142913828922 |
142913828922 |
||
Line 388: | Line 388: | ||
=={{header|Pascal}}== |
=={{header|Pascal}}== |
||
uses {{libheader|primTrial}} |
uses {{libheader|primTrial}} |
||
< |
<syntaxhighlight lang="pascal"> |
||
program SumPrimes; |
program SumPrimes; |
||
{$IFDEF FPC}{$MODE DELPHI}{$OPTIMIZATION ON,ALL} |
{$IFDEF FPC}{$MODE DELPHI}{$OPTIMIZATION ON,ALL} |
||
Line 402: | Line 402: | ||
writeln(sum); |
writeln(sum); |
||
{$IFDEF WINDOWS} readln;{$ENDIF} |
{$IFDEF WINDOWS} readln;{$ENDIF} |
||
end.</ |
end.</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 408: | Line 408: | ||
=={{header|Perl}}== |
=={{header|Perl}}== |
||
< |
<syntaxhighlight lang="perl">#!/usr/bin/perl |
||
use strict; # https://rosettacode.org/wiki/Summation_of_primes |
use strict; # https://rosettacode.org/wiki/Summation_of_primes |
||
Line 415: | Line 415: | ||
use List::Util qw( sum ); |
use List::Util qw( sum ); |
||
print sum( @{ primes( 2e6 ) } ), "\n";</ |
print sum( @{ primes( 2e6 ) } ), "\n";</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 422: | Line 422: | ||
=={{header|Phix}}== |
=={{header|Phix}}== |
||
<!--< |
<!--<syntaxhighlight lang="phix">(phixonline)--> |
||
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"The sum of primes below 2 million is %,d\n"</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">sum</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">get_primes_le</span><span style="color: #0000FF;">(</span><span style="color: #000000;">2e6</span><span style="color: #0000FF;">)))</span> |
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"The sum of primes below 2 million is %,d\n"</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">sum</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">get_primes_le</span><span style="color: #0000FF;">(</span><span style="color: #000000;">2e6</span><span style="color: #0000FF;">)))</span> |
||
<!--</ |
<!--</syntaxhighlight>--> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 433: | Line 433: | ||
=={{header|Python}}== |
=={{header|Python}}== |
||
===Procedural=== |
===Procedural=== |
||
< |
<syntaxhighlight lang="python">#!/usr/bin/python |
||
def isPrime(n): |
def isPrime(n): |
||
Line 448: | Line 448: | ||
suma += i |
suma += i |
||
n+=1 |
n+=1 |
||
print(suma)</ |
print(suma)</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>142913828922</pre> |
<pre>142913828922</pre> |
||
===Functional=== |
===Functional=== |
||
< |
<syntaxhighlight lang="python">'''Summatiom of primes''' |
||
from functools import reduce |
from functools import reduce |
||
Line 497: | Line 497: | ||
# MAIN --- |
# MAIN --- |
||
if __name__ == '__main__': |
if __name__ == '__main__': |
||
main()</ |
main()</syntaxhighlight> |
||
{{Out}} |
{{Out}} |
||
<pre>142913828922</pre> |
<pre>142913828922</pre> |
||
Line 504: | Line 504: | ||
Or, more efficiently, assuming that we have a generator of primes: |
Or, more efficiently, assuming that we have a generator of primes: |
||
< |
<syntaxhighlight lang="python">'''Summatiom of primes''' |
||
from itertools import count, takewhile |
from itertools import count, takewhile |
||
Line 568: | Line 568: | ||
# MAIN --- |
# MAIN --- |
||
if __name__ == '__main__': |
if __name__ == '__main__': |
||
main()</ |
main()</syntaxhighlight> |
||
{{Out}} |
{{Out}} |
||
<pre>142913828922</pre> |
<pre>142913828922</pre> |
||
Line 574: | Line 574: | ||
=={{header|Raku}}== |
=={{header|Raku}}== |
||
Slow, but only using compiler built-ins (about 5 seconds) |
Slow, but only using compiler built-ins (about 5 seconds) |
||
<lang |
<syntaxhighlight lang="raku" line>say sum (^2e6).grep: {.&is-prime};</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>142913828922</pre> |
<pre>142913828922</pre> |
||
Much faster using external libraries (well under half a second) |
Much faster using external libraries (well under half a second) |
||
<lang |
<syntaxhighlight lang="raku" line>use Math::Primesieve; |
||
my $sieve = Math::Primesieve.new; |
my $sieve = Math::Primesieve.new; |
||
say sum $sieve.primes(2e6.Int);</ |
say sum $sieve.primes(2e6.Int);</syntaxhighlight> |
||
Same output |
Same output |
||
=={{header|Ring}}== |
=={{header|Ring}}== |
||
< |
<syntaxhighlight lang="ring"> |
||
load "stdlib.ring" |
load "stdlib.ring" |
||
see "working..." + nl |
see "working..." + nl |
||
Line 600: | Line 600: | ||
see "" + sum + nl |
see "" + sum + nl |
||
see "done..." + nl |
see "done..." + nl |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 610: | Line 610: | ||
=={{header|Ruby}}== |
=={{header|Ruby}}== |
||
<lang |
<syntaxhighlight lang="ruby">puts Prime.each(2_000_000).sum</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>142913828922 |
<pre>142913828922 |
||
Line 618: | Line 618: | ||
Built-in: |
Built-in: |
||
< |
<syntaxhighlight lang="ruby">say sum_primes(2e6) #=> 142913828922</syntaxhighlight> |
||
Linear algorithm: |
Linear algorithm: |
||
< |
<syntaxhighlight lang="ruby">func sum_primes(limit) { |
||
var sum = 0 |
var sum = 0 |
||
for (var p = 2; p < limit; p.next_prime!) { |
for (var p = 2; p < limit; p.next_prime!) { |
||
Line 629: | Line 629: | ||
} |
} |
||
say sum_primes(2e6)</ |
say sum_primes(2e6)</syntaxhighlight> |
||
Sublinear algorithm: |
Sublinear algorithm: |
||
< |
<syntaxhighlight lang="ruby">func sum_of_primes(n) { |
||
return 0 if (n <= 1) |
return 0 if (n <= 1) |
||
Line 655: | Line 655: | ||
} |
} |
||
say sum_of_primes(2e6)</ |
say sum_of_primes(2e6)</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 664: | Line 664: | ||
{{libheader|Wren-math}} |
{{libheader|Wren-math}} |
||
{{libheader|Wren-fmt}} |
{{libheader|Wren-fmt}} |
||
< |
<syntaxhighlight lang="ecmascript">import "./math" for Int, Nums |
||
import "./fmt" for Fmt |
import "./fmt" for Fmt |
||
Fmt.print("The sum of all primes below 2 million is $,d.", Nums.sum(Int.primeSieve(2e6-1)))</ |
Fmt.print("The sum of all primes below 2 million is $,d.", Nums.sum(Int.primeSieve(2e6-1)))</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 676: | Line 676: | ||
=={{header|XPL0}}== |
=={{header|XPL0}}== |
||
Takes 3.7 seconds on Pi4. |
Takes 3.7 seconds on Pi4. |
||
< |
<syntaxhighlight lang="xpl0">func IsPrime(N); \Return 'true' if N is a prime number >= 3 |
||
int N, I; |
int N, I; |
||
[if (N&1) = 0 then return false; \N is even |
[if (N&1) = 0 then return false; \N is even |
||
Line 693: | Line 693: | ||
Format(1, 0); \don't show places after decimal point |
Format(1, 0); \don't show places after decimal point |
||
RlOut(0, Sum); |
RlOut(0, Sum); |
||
]</ |
]</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 702: | Line 702: | ||
=={{header|Yabasic}}== |
=={{header|Yabasic}}== |
||
{{trans|Python}} |
{{trans|Python}} |
||
< |
<syntaxhighlight lang="yabasic">// Rosetta Code problem: http://rosettacode.org/wiki/Summation_of_primes |
||
// by Galileo, 04/2022 |
// by Galileo, 04/2022 |
||
Line 718: | Line 718: | ||
if isPrime(i) suma = suma + i |
if isPrime(i) suma = suma + i |
||
next |
next |
||
print str$(suma, "%12.f")</ |
print str$(suma, "%12.f")</syntaxhighlight> |
Revision as of 17:54, 28 August 2022
- Task
The task description is taken from Project Euler (https://projecteuler.net/problem=10)
The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17
Find the sum of all the primes below two million
ALGOL 68
BEGIN # sum primes up to 2 000 000 #
PR read "primes.incl.a68" PR
# return s space-separated into groups of 3 digits #
PROC space separate = ( STRING unformatted )STRING:
BEGIN
STRING result := "";
INT ch count := 0;
FOR c FROM UPB unformatted BY -1 TO LWB unformatted DO
IF ch count <= 2 THEN ch count +:= 1
ELSE ch count := 1; " " +=: result
FI;
unformatted[ c ] +=: result
OD;
result
END # space separate # ;
# sum the primes #
[]BOOL prime = PRIMESIEVE 2 000 000;
LONG INT sum := 2;
FOR i FROM 3 BY 2 TO UPB prime DO
IF prime[ i ] THEN
sum +:= i
FI
OD;
print( ( space separate( whole( sum, 0 ) ), newline ) )
END
- Output:
142 913 828 922
AppleScript
This isn't something that's likely to needed more than once — if at all — so you'd probably just throw together code like the following. The result's interesting in that although it's way outside AppleScript's integer range, its class is returned as integer in macOS 10.14 (Mojave)!
on isPrime(n)
if ((n < 4) or (n is 5)) then return (n > 1)
if ((n mod 2 = 0) or (n mod 3 = 0) or (n mod 5 = 0)) then return false
repeat with i from 7 to (n ^ 0.5) div 1 by 30
if ((n mod i = 0) or (n mod (i + 4) = 0) or (n mod (i + 6) = 0) or ¬
(n mod (i + 10) = 0) or (n mod (i + 12) = 0) or (n mod (i + 16) = 0) or ¬
(n mod (i + 22) = 0) or (n mod (i + 24) = 0)) then return false
end repeat
return true
end isPrime
on sumPrimes below this
set limit to this - 1
if (limit < 2) then return 0
set sum to 2
repeat with n from 3 to limit by 2
if (isPrime(n)) then set sum to sum + n
end repeat
return sum
end sumPrimes
sumPrimes below 2000000
- Output:
142913828922
The result can be obtained in 4 seconds rather than 14 if the summing's instead combined with an Eratosthenean sieve:
on sumPrimes below this
set limit to this - 1
-- Is the limit 2 or lower?
if (limit = 2) then return 2
if (limit < 2) then return 0
-- Build a list of limit (+ 2 for safety) missing values.
set mv to missing value
script o
property numberList : {mv}
end script
repeat until ((count o's numberList) * 2 > limit)
set o's numberList to o's numberList & o's numberList
end repeat
set o's numberList to {mv} & items 1 thru (limit - (count o's numberList) + 1) of o's numberList & o's numberList
-- Populate every 6th slot after the 5th and 7th with the equivalent integers.
-- The other slots all represent multiples of 2 and/or 3 and are left as missing values.
repeat with n from 5 to limit by 6
set item n of o's numberList to n
tell (n + 2) to set item it of o's numberList to it
end repeat
-- If we're here, the limit must be 3 or higher. So start with the sum of 2 and 3.
set sum to 5
-- Continue adding primes from the list and eliminate multiples
-- of those up to the limit's square root from the list.
set isqrt to limit ^ 0.5 div 1
repeat with n from 5 to limit by 6
if (item n of o's numberList = n) then
set sum to sum + n
if (n ≤ isqrt) then
repeat with multiple from (n * n) to limit by n
set item multiple of o's numberList to mv
end repeat
end if
end if
tell (n + 2)
if ((it ≤ limit) and (item it of o's numberList = it)) then
set sum to sum + it
if (it ≤ isqrt) then
repeat with multiple from (it * it) to limit by it
set item multiple of o's numberList to mv
end repeat
end if
end if
end tell
end repeat
return sum
end sumPrimes
sumPrimes below 2000000
AWK
# syntax: GAWK -f SUMMATION_OF_PRIMES.AWK
BEGIN {
main(10)
main(2000000)
exit(0)
}
function main(stop, count,sum) {
if (stop < 3) {
return
}
count = 1
sum = 2
for (i=3; i<stop; i+=2) {
if (is_prime(i)) {
sum += i
count++
}
}
printf("The %d primes below %d sum to %d\n",count,stop,sum)
}
function is_prime(n, d) {
d = 5
if (n < 2) { return(0) }
if (n % 2 == 0) { return(n == 2) }
if (n % 3 == 0) { return(n == 3) }
while (d*d <= n) {
if (n % d == 0) { return(0) }
d += 2
if (n % d == 0) { return(0) }
d += 4
}
return(1)
}
- Output:
The 4 primes below 10 sum to 17 The 148933 primes below 2000000 sum to 142913828922
BASIC
FreeBASIC
#include "isprime.bas"
dim as integer sum = 2, i, n=1
for i = 3 to 2000000 step 2
if isprime(i) then
sum += i
n+=1
end if
next i
print sum
- Output:
142913828922
GW-BASIC
10 S# = 2
20 FOR P = 3 TO 1999999! STEP 2
30 GOSUB 80
40 IF Q=1 THEN S#=S#+P
50 NEXT P
60 PRINT S#
70 END
80 Q=0
90 IF P=3 THEN Q=1:RETURN
100 I=1
110 I=I+2
120 IF INT(P/I)*I = P THEN RETURN
130 IF I*I<=P THEN GOTO 110
140 Q = 1
150 RETURN
- Output:
142913828922
C
#include<stdio.h>
#include<stdlib.h>
int isprime( int p ) {
int i;
if(p==2) return 1;
if(!(p%2)) return 0;
for(i=3; i*i<=p; i+=2) {
if(!(p%i)) return 0;
}
return 1;
}
int main( void ) {
int p;
long int s = 2;
for(p=3;p<2000000;p+=2) {
if(isprime(p)) s+=p;
}
printf( "%ld\n", s );
return 0;
}
- Output:
142913828922
CLU
isqrt = proc (s: int) returns (int)
x0: int := s/2
if x0=0 then
return(s)
else
x1: int := (x0 + s/x0) / 2
while x1<x0 do
x0 := x1
x1 := (x0 + s/x0) / 2
end
return(x0)
end
end isqrt
sieve = proc (top: int) returns (array[bool])
prime: array[bool] := array[bool]$fill(2,top-1,true)
for p: int in int$from_to(2,isqrt(top)) do
for c: int in int$from_to_by(p*p,top,p) do
prime[c] := false
end
end
return(prime)
end sieve
sum_primes_to = proc (top: int) returns (int)
sum: int := 0
prime: array[bool] := sieve(top)
for i: int in array[bool]$indexes(prime) do
if prime[i] then sum := sum+i end
end
return(sum)
end sum_primes_to
start_up = proc ()
stream$putl(stream$primary_output(), int$unparse(sum_primes_to(2000000)))
end start_up
- Output:
142913828922
Crystal
def prime?(n) # P3 Prime Generator primality test
return false unless (n | 1 == 3 if n < 5) || (n % 6) | 4 == 5
sqrt = Math.isqrt(n)
pc = typeof(n).new(5)
while pc <= sqrt
return false if n % pc == 0 || n % (pc + 2) == 0
pc += 6
end
true
end
puts "The sum of all primes below 2 million is #{(0i64..2000000i64).select { |n| n if prime? n }.sum}."
#also
puts "The sum of all primes below 2 million is #{(0i64..2000000i64).sum { |n| prime?(n) ? n : 0u64 }}"
- Output:
The sum of all primes below 2 million is 142913828923.
F#
This task uses Extensible Prime Generator (F#)
// Summation of primes. Nigel Galloway: November 9th., 2021
printfn $"%d{primes64()|>Seq.takeWhile((>)2000000L)|>Seq.sum}"
- Output:
142913828922
Factor
USING: math.primes prettyprint sequences ;
2,000,000 primes-upto sum .
- Output:
142913828922
Fermat
s:=2;
for p=3 to 1999999 by 2 do if Isprime(p) then s:=s+p fi od;
!!s;
- Output:
142913828922
Go
package main
import (
"fmt"
"rcu"
)
func main() {
sum := 0
for _, p := range rcu.Primes(2e6 - 1) {
sum += p
}
fmt.Printf("The sum of all primes below 2 million is %s.\n", rcu.Commatize(sum))
}
- Output:
The sum of all primes below 2 million is 142,913,828,922.
Haskell
import Data.Numbers.Primes (primes)
sumOfPrimesBelow :: Integral a => a -> a
sumOfPrimesBelow n =
sum $ takeWhile (< n) primes
main :: IO ()
main = print $ sumOfPrimesBelow 2000000
- Output:
142913828922
jq
Works with gojq, the Go implementation of jq
See Erdős-primes#jq for a suitable definition of `is_prime/1` as used here.
def sum(s): reduce s as $x (0; .+$x);
sum(2, range(3 ; 2E6; 2) | select(is_prime))
- Output:
142913828922
Julia
using Primes
@show sum(primes(2_000_000)) # sum(primes(2000000)) = 142913828922
Mathematica / Wolfram Language
Total[Most@NestWhileList[NextPrime, 2, # < 2000000 &]]
- Output:
142913828922
PARI/GP
s=2; p=3
while(p<2000000,if(isprime(p),s=s+p);p=p+2)
print(s)
- Output:
142913828922
Pascal
uses
program SumPrimes;
{$IFDEF FPC}{$MODE DELPHI}{$OPTIMIZATION ON,ALL}
{$ELSE} {$APPTYPE CONSOLE}
{$ENDIF}
uses
SysUtils,primTrial;
var
p,sum : NativeInt;
begin
sum := actPrime;
repeat inc(sum,p); p := NextPrime until p >= 2*1000*1000;
writeln(sum);
{$IFDEF WINDOWS} readln;{$ENDIF}
end.
- Output:
142913828922
Perl
#!/usr/bin/perl
use strict; # https://rosettacode.org/wiki/Summation_of_primes
use warnings;
use ntheory qw( primes );
use List::Util qw( sum );
print sum( @{ primes( 2e6 ) } ), "\n";
- Output:
142913828922
Phix
printf(1,"The sum of primes below 2 million is %,d\n",sum(get_primes_le(2e6)))
- Output:
The sum of primes below 2 million is 142,913,828,922
Python
Procedural
#!/usr/bin/python
def isPrime(n):
for i in range(2, int(n**0.5) + 1):
if n % i == 0:
return False
return True
if __name__ == '__main__':
suma = 2
n = 1
for i in range(3, 2000000, 2):
if isPrime(i):
suma += i
n+=1
print(suma)
- Output:
142913828922
Functional
'''Summatiom of primes'''
from functools import reduce
# sumOfPrimesBelow :: Int -> Int
def sumOfPrimesBelow(n):
'''Sum of all primes between 2 and n'''
def go(a, x):
return a + x if isPrime(x) else a
return reduce(go, range(2, n), 0)
# ------------------------- TEST -------------------------
# main :: IO ()
def main():
'''Sum of primes below 2 million'''
print(
sumOfPrimesBelow(2_000_000)
)
# ----------------------- GENERIC ------------------------
# isPrime :: Int -> Bool
def isPrime(n):
'''True if n is prime.'''
if n in (2, 3):
return True
if 2 > n or 0 == n % 2:
return False
if 9 > n:
return True
if 0 == n % 3:
return False
def p(x):
return 0 == n % x or 0 == n % (2 + x)
return not any(map(p, range(5, 1 + int(n ** 0.5), 6)))
# MAIN ---
if __name__ == '__main__':
main()
- Output:
142913828922
Or, more efficiently, assuming that we have a generator of primes:
'''Summatiom of primes'''
from itertools import count, takewhile
# sumOfPrimesBelow :: Int -> Int
def sumOfPrimesBelow(n):
'''Sum of all primes between 2 and n'''
return sum(takewhile(lambda x: n > x, primes()))
# ------------------------- TEST -------------------------
# main :: IO ()
def main():
'''Sum of primes below 2 million'''
print(
sumOfPrimesBelow(2_000_000)
)
# ----------------------- GENERIC ------------------------
# enumFromThen :: Int -> Int -> [Int]
def enumFromThen(m):
'''A non-finite stream of integers
starting at m, and continuing
at the interval between m and n.
'''
return lambda n: count(m, n - m)
# primes :: [Int]
def primes():
'''An infinite stream of primes.'''
seen = {}
yield 2
p = None
for q in enumFromThen(3)(5):
p = seen.pop(q, None)
if p is None:
seen[q ** 2] = q
yield q
else:
seen[
until(
lambda x: x not in seen,
lambda x: x + 2 * p,
q + 2 * p
)
] = p
# until :: (a -> Bool) -> (a -> a) -> a -> a
def until(p, f, v):
'''The result of repeatedly applying f until p holds.
The initial seed value is x.
'''
while not p(v):
v = f(v)
return v
# MAIN ---
if __name__ == '__main__':
main()
- Output:
142913828922
Raku
Slow, but only using compiler built-ins (about 5 seconds)
say sum (^2e6).grep: {.&is-prime};
- Output:
142913828922
Much faster using external libraries (well under half a second)
use Math::Primesieve;
my $sieve = Math::Primesieve.new;
say sum $sieve.primes(2e6.Int);
Same output
Ring
load "stdlib.ring"
see "working..." + nl
sum = 2
limit = 2000000
for n = 3 to limit step 2
if isprime(n)
sum += n
ok
next
see "The sum of all the primes below two million:" + nl
see "" + sum + nl
see "done..." + nl
- Output:
working... The sum of all the primes below two million: 142,913,828,922 done...
Ruby
puts Prime.each(2_000_000).sum
- Output:
142913828922
Sidef
Built-in:
say sum_primes(2e6) #=> 142913828922
Linear algorithm:
func sum_primes(limit) {
var sum = 0
for (var p = 2; p < limit; p.next_prime!) {
sum += p
}
return sum
}
say sum_primes(2e6)
Sublinear algorithm:
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)
- Output:
142913828922
Wren
import "./math" for Int, Nums
import "./fmt" for Fmt
Fmt.print("The sum of all primes below 2 million is $,d.", Nums.sum(Int.primeSieve(2e6-1)))
- Output:
The sum of all primes below 2 million is 142,913,828,922.
XPL0
Takes 3.7 seconds on Pi4.
func IsPrime(N); \Return 'true' if N is a prime number >= 3
int N, I;
[if (N&1) = 0 then return false; \N is even
for I:= 3 to sqrt(N) do
[if rem(N/I) = 0 then return false;
I:= I+1; \step by 2 (=1+1)
];
return true;
];
real Sum; \provides 15 decimal digits
int N; \provides 9 decimal digits
[Sum:= 2.; \2 is prime
for N:= 3 to 2_000_000 do
if IsPrime(N) then Sum:= Sum + float(N);
Format(1, 0); \don't show places after decimal point
RlOut(0, Sum);
]
- Output:
142913828922
Yabasic
// Rosetta Code problem: http://rosettacode.org/wiki/Summation_of_primes
// by Galileo, 04/2022
sub isPrime(n)
local i
for i = 2 to sqrt(n)
if mod(n, i) = 0 return False
next
return True
end sub
suma = 2
for i = 3 to 2000000 step 2
if isPrime(i) suma = suma + i
next
print str$(suma, "%12.f")