Jump to content

Summation of primes

From Rosetta Code
Revision as of 14:42, 3 December 2022 by Tigerofdarkness (talk | contribs) (→{{header|ALGOL 68}}: Fix layout)
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
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

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 

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: 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

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 

#!/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

Quackery

eratosthenes and isprime are defined atSieve of Eratosthenes#Quackery. 

  2000000 eratosthenes
 
  0 2000000 times [ i isprime if [ i + ] ] echo
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

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

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

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")
Retrieved from "https://rosettacode.org/wiki/Summation_of_primes?oldid=334059"
Cookies help us deliver our services. By using our services, you agree to our use of cookies.
More information