Summation of primes
- 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
<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
AWK
<lang 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)
} </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>
- 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 pc = typeof(n).new(5) while pc <= Math.isqrt(n) 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 }}"
</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
<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 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
<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
- 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()</lang>
- Output:
142913828922
Or, more efficiently, assuming that we have a generator of primes:
<lang python>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()</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
<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
<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>