Summation of primes

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

Library: ALGOL 68-primes

<lang algol68>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</lang>

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)!

<lang applescript>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</lang>

Output:

<lang applescript>142913828922</lang>

The result can be obtained in 4 seconds rather than 14 if the summing's instead combined with an Eratosthenean sieve:

<lang applescript>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</lang>

AWK

<lang AWK>

1. 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)

} </lang>

Output:

The 4 primes below 10 sum to 17
The 148933 primes below 2000000 sum to 142913828922

BASIC

FreeBASIC

<lang 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</lang>

Output:

142913828922

GW-BASIC

<lang gwbasic>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 </lang>

Output:

142913828922

C

<lang c>#include<stdio.h>

1. 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;

}</lang>

Output:

142913828922

CLU

<lang 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 </lang>

Output:

142913828922

Crystal

<lang ruby>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}."

1. also

puts "The sum of all primes below 2 million is #{(0i64..2000000i64).sum { |n| prime?(n) ? n : 0u64 }}"

</lang>

Output:

The sum of all primes below 2 million is 142913828923.

F#

This task uses Extensible Prime Generator (F#) <lang fsharp> // Summation of primes. Nigel Galloway: November 9th., 2021 printfn $"%d{primes64()|>Seq.takeWhile((>)2000000L)|>Seq.sum}" </lang>

Output:

142913828922

Factor

<lang factor>USING: math.primes prettyprint sequences ;

2,000,000 primes-upto sum .</lang>

Output:

142913828922

Fermat

<lang fermat>s:=2; for p=3 to 1999999 by 2 do if Isprime(p) then s:=s+p fi od; !!s;</lang>

Output:

142913828922

Go

Library: Go-rcu

<lang 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))

}</lang>

Output:

The sum of all primes below 2 million is 142,913,828,922.

Haskell

<lang haskell>import Data.Numbers.Primes (primes)

sumOfPrimesBelow :: Integral a => a -> a sumOfPrimesBelow n =

 sum $ takeWhile (< n) primes

main :: IO () main = print $ sumOfPrimesBelow 2000000</lang>

Output:

142913828922

jq

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. <lang jq>def sum(s): reduce s as $x (0; .+$x);

sum(2, range(3 ; 2E6; 2) | select(is_prime))</lang>

Output:

142913828922

Julia

<lang julia>using Primes

@show sum(primes(2_000_000)) # sum(primes(2000000)) = 142913828922 </lang>

Mathematica / Wolfram Language

<lang Mathematica>Total[Most@NestWhileList[NextPrime, 2, # < 2000000 &]]</lang>

Output:

142913828922

PARI/GP

<lang parigp> s=2; p=3 while(p<2000000,if(isprime(p),s=s+p);p=p+2) print(s) </lang>

Output:

142913828922

Pascal

uses

Library: primTrial

<lang pascal> 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.</lang>

Output:

142913828922

Perl

<lang 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";</lang>

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

<lang python>#!/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)</lang>

Output:

142913828922

Functional

<lang python>Summatiom of primes

from functools import reduce

1. 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)

1. ------------------------- TEST -------------------------
2. main :: IO ()

def main():

   Sum of primes below 2 million
   print(
       sumOfPrimesBelow(2_000_000)
   )

1. ----------------------- GENERIC ------------------------

1. 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)))

1. MAIN ---

if __name__ == '__main__':

   main()</lang>

Output:

142913828922

Or, more efficiently, assuming that we have a generator of primes:

<lang python>Summatiom of primes

from itertools import count, takewhile

1. sumOfPrimesBelow :: Int -> Int

def sumOfPrimesBelow(n):

   Sum of all primes between 2 and n
   return sum(takewhile(lambda x: n > x, primes()))

1. ------------------------- TEST -------------------------
2. main :: IO ()

def main():

   Sum of primes below 2 million
   print(
       sumOfPrimesBelow(2_000_000)
   )

1. ----------------------- GENERIC ------------------------

1. 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)

1. 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

1. 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

1. MAIN ---

if __name__ == '__main__':

   main()</lang>

Output:

142913828922

Raku

Slow, but only using compiler built-ins (about 5 seconds) <lang perl6>say sum (^2e6).grep: {.&is-prime};</lang>

Output:

142913828922

Much faster using external libraries (well under half a second) <lang perl6>use Math::Primesieve; my $sieve = Math::Primesieve.new; say sum $sieve.primes(2e6.Int);</lang> Same output

Ring

<lang 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 </lang>

Output:

working...
The sum of all the primes below two million:
142,913,828,922
done...

Ruby

<lang ruby>puts Prime.each(2_000_000).sum </lang>

Output:

142913828922

Wren

Library: Wren-math

Library: Wren-fmt

<lang ecmascript>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)))</lang>

Output:

The sum of all primes below 2 million is 142,913,828,922.

XPL0

Takes 3.7 seconds on Pi4. <lang XPL0>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); ]</lang>

Output:

142913828922

Yabasic

Translation of: Python

<lang 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")</lang>