I'm working on modernizing Rosetta Code's infrastructure. Starting with communications. Please accept this time-limited open invite to RC's Slack.. --Michael Mol (talk) 20:59, 30 May 2020 (UTC)

Summation of primes

From Rosetta Code
Summation of primes is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.
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[edit]

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[edit]

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[edit]

 
# 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[edit]

FreeBASIC[edit]

#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[edit]

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[edit]

#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[edit]

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[edit]

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#[edit]

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[edit]

USING: math.primes prettyprint sequences ;
 
2,000,000 primes-upto sum .
Output:
142913828922

Fermat[edit]

s:=2;
for p=3 to 1999999 by 2 do if Isprime(p) then s:=s+p fi od;
!!s;
Output:
142913828922

Go[edit]

Library: Go-rcu
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[edit]

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[edit]

Works with: 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[edit]

using Primes
 
@show sum(primes(2_000_000)) # sum(primes(2000000)) = 142913828922
 

Mathematica / Wolfram Language[edit]

Total[[email protected][NextPrime, 2, # < 2000000 &]]
Output:

142913828922

PARI/GP[edit]

 
s=2; p=3
while(p<2000000,if(isprime(p),s=s+p);p=p+2)
print(s)
 
Output:

142913828922

Pascal[edit]

uses
Library: primTrial
 
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[edit]

#!/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[edit]

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[edit]

Procedural[edit]

#!/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[edit]

'''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[edit]

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[edit]

 
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[edit]

puts Prime.each(2_000_000).sum
 
Output:
142913828922

Wren[edit]

Library: Wren-math
Library: Wren-fmt
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[edit]

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[edit]

Translation of: Python
// 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")