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[Most@NestWhileList[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

Sidef[edit]

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[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")