Rosetta Code

Summation of primes: Difference between revisions

Page Discussion

Summation of primes (view source)

Revision as of 15:59, 16 April 2024

17,168 bytes added ,  1 month ago
no edit summary
(→‎{{header|ALGOL 68}}: no need to check even numbers... doh!)
No edit summary
 
(40 intermediate revisions by 28 users not shown)
Line 9:
=={{header|ALGOL 68}}==
{{libheader|ALGOL 68-primes}}
<langsyntaxhighlight 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 #
Line 28:
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</langsyntaxhighlight>
{{out}}
<pre>
142 913 828 922
</pre>
 
=={{header|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)!
 
<syntaxhighlight 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</syntaxhighlight>
 
{{output}}
<syntaxhighlight lang="applescript">142913828922</syntaxhighlight>
 
The result can be obtained in 4 seconds rather than 14 if the summing's instead combined with an Eratosthenean sieve:
 
<syntaxhighlight 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</syntaxhighlight>
 
=={{header|Arturo}}==
 
<syntaxhighlight lang="arturo">print sum select 2..2000000 => prime?</syntaxhighlight>
 
{{out}}
 
<pre>142913828922</pre>
 
=={{header|AWK}}==
<syntaxhighlight 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)
}
</syntaxhighlight>
{{out}}
<pre>
The 4 primes below 10 sum to 17
The 148933 primes below 2000000 sum to 142913828922
</pre>
 
=={{header|BASIC}}==
==={{header|FreeBASIC}}===
<langsyntaxhighlight lang="freebasic">#include "isprime.bas"
 
dim as integer sum = 2, i, n=1
Line 51 ⟶ 188:
next i
 
print sum</langsyntaxhighlight>
{{out}}<pre>142913828922</pre>
 
==={{header|GW-BASIC}}===
<langsyntaxhighlight lang="gwbasic">10 S# = 2
20 FOR P = 3 TO 1999999! STEP 2
30 GOSUB 80
Line 70 ⟶ 207:
140 Q = 1
150 RETURN
</syntaxhighlight>
</lang>
{{out}}<pre>142913828922</pre>
 
=={{header|C}}==
<langsyntaxhighlight lang="c">#include<stdio.h>
#include<stdlib.h>
 
Line 95 ⟶ 232:
printf( "%ld\n", s );
return 0;
}</langsyntaxhighlight>
{{out}}<pre>142913828922</pre>
 
=={{header|CLU}}==
<syntaxhighlight 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 </syntaxhighlight>
{{out}}
<pre>142913828922</pre>
 
=={{header|Crystal}}==
<syntaxhighlight 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}."
 
#also
 
puts "The sum of all primes below 2 million is #{(0i64..2000000i64).sum { |n| prime?(n) ? n : 0u64 }}"
 
</syntaxhighlight>
{{out}}
<pre>The sum of all primes below 2 million is 142913828923.
</pre>
 
=={{header|Delphi}}==
{{works with|Delphi|6.0}}
{{libheader|SysUtils,StdCtrls}}
 
 
<syntaxhighlight lang="Delphi">
 
procedure SummationOfPrimes(Memo: TMemo);
var I: integer;
var Sum: int64;
var Sieve: TPrimeSieve;
begin
Sieve:=TPrimeSieve.Create;
try
Sieve.Intialize(2000000);
Sum:=0;
for I:=0 to Sieve.PrimeCount-1 do
Sum:=Sum+Sieve.Primes[I];
Memo.Lines.Add(Format('Sum of Primes Below 2 million: %.0n',[Sum+0.0]));
finally Sieve.Free; end;
end;
 
 
</syntaxhighlight>
{{out}}
<pre>
Sum of Primes Below 2 million: 142,913,828,922
 
Elapsed Time: 17.405 ms.
</pre>
 
 
=={{header|F_Sharp|F#}}==
This task uses [http://www.rosettacode.org/wiki/Extensible_prime_generator#The_functions Extensible Prime Generator (F#)]
<syntaxhighlight lang="fsharp">
// Summation of primes. Nigel Galloway: November 9th., 2021
printfn $"%d{primes64()|>Seq.takeWhile((>)2000000L)|>Seq.sum}"
</syntaxhighlight>
{{out}}
<pre>
142913828922
</pre>
 
=={{header|Factor}}==
<syntaxhighlight lang="factor">USING: math.primes prettyprint sequences ;
 
2,000,000 primes-upto sum .</syntaxhighlight>
{{out}}
<pre>
142913828922
</pre>
 
=={{header|Fermat}}==
<langsyntaxhighlight lang="fermat">s:=2;
for p=3 to 1999999 by 2 do if Isprime(p) then s:=s+p fi od;
!!s;</langsyntaxhighlight>
{{out}}<pre>142913828922</pre>
 
=={{header|FutureBasic}}==
<syntaxhighlight lang="futurebasic">
local fn IsPrime( n as NSUInteger ) as BOOL
BOOL isPrime = YES
NSUInteger i
if n < 2 then exit fn = NO
if n = 2 then exit fn = YES
if n mod 2 == 0 then exit fn = NO
for i = 3 to int(n^.5) step 2
if n mod i == 0 then exit fn = NO
next
end fn = isPrime
 
 
local fn SumOfPrimes as long
long sum = 2, i, n = 1
for i = 3 to 2000000 step 2
if ( fn IsPrime(i) )
sum += i
n++
end if
next
end fn = sum
 
print fn SumOfPrimes
 
HandleEvents
</syntaxhighlight>
{{output}}
<pre>
142913828922
</pre>
 
 
=={{header|Go}}==
{{libheader|Go-rcu}}
<langsyntaxhighlight lang="go">package main
 
import (
Line 119 ⟶ 407:
}
fmt.Printf("The sum of all primes below 2 million is %s.\n", rcu.Commatize(sum))
}</langsyntaxhighlight>
 
{{out}}
Line 126 ⟶ 414:
</pre>
 
 
=={{header|Haskell}}==
<syntaxhighlight lang="haskell">import Data.Numbers.Primes (primes)
 
sumOfPrimesBelow :: Integral a => a -> a
sumOfPrimesBelow n =
sum $ takeWhile (< n) primes
 
main :: IO ()
main = print $ sumOfPrimesBelow 2000000</syntaxhighlight>
{{Out}}
<pre>142913828922</pre>
 
 
=={{header|J}}==
<syntaxhighlight lang=J>+/p: i. p:inv 2e6
142913828922</syntaxhighlight>
 
Here, p: represents what might be thought of as an array of primes, and its argument represents array indices of those primes. Similarly, the result p:inv represents the smallest index whose prime is no less than its argument.
 
So...
<syntaxhighlight lang=J> p:inv 2e6
148933
p: p:inv 2e6
2000003</syntaxhighlight>
 
Also, <code>i. n</code> returns a list of indices starting at zero and ending at one less than n (assuming n is a positive integer which of course it is, here).
 
And, (for people not familiar with J): <code>+/</code> sums a list (evaluates the hypothetical expression which would result from insert <code>+</code> between each element of that list).
 
=={{header|jq}}==
{{works with|jq}}
'''Works with gojq, the Go implementation of jq'''
 
See [[Erd%C5%91s-primes#jq]] for a suitable definition of `is_prime/1` as used here.
<syntaxhighlight lang="jq">def sum(s): reduce s as $x (0; .+$x);
 
sum(2, range(3 ; 2E6; 2) | select(is_prime))</syntaxhighlight>
{{out}}
<pre>
142913828922
</pre>
 
=={{header|Julia}}==
<langsyntaxhighlight lang="julia">using Primes
 
@show sum(primes(2_000_000)) # sum(primes(2000000)) = 142913828922
</syntaxhighlight>
</lang>
=={{header|Mathematica}} / {{header|Wolfram Language}}==
<syntaxhighlight lang="mathematica">Total[Most@NestWhileList[NextPrime, 2, # < 2000000 &]]</syntaxhighlight>
 
{{out}}<pre>
142913828922
</pre>
 
 
=={{header|Maxima}}==
<syntaxhighlight lang="maxima">
block(primes(2,2000000),apply("+",%%));
</syntaxhighlight>
Output
<syntaxhighlight lang="maxima">
/* 142913828922 */
</syntaxhighlight>
 
=={{header|Nim}}==
<syntaxhighlight lang="Nim">func isPrime(n: Natural): bool =
## Return true if "n" is prime.
## "n" is expected not to be a multiple of 2 or 3.
var k = 5
while k * k <= n:
if n mod k == 0 or n mod (k + 2) == 0: return false
inc k, 6
result = true
 
var sum = 2 + 3
var n = 5
while n < 2_000_000:
if n.isPrime:
inc sum, n
inc n, 2
if n.isPrime:
inc sum, n
inc n, 4
 
echo sum
</syntaxhighlight>
 
{{out}}
<pre>142913828922</pre>
 
=={{header|PARI/GP}}==
<langsyntaxhighlight lang="parigp">
s=2; p=3
while(p<2000000,if(isprime(p),s=s+p);p=p+2)
print(s)
</syntaxhighlight>
</lang>
{{out}}<pre>
142913828922
</pre>
=={{header|Pascal}}==
uses {{libheader|primTrialprimsieve}} [[Extensible_prime_generator#Pascal|Extensible_prime_generator]]
<langsyntaxhighlight lang="pascal">
program SumPrimes;
{$IFDEF FPC}{$MODE DELPHI}{$OPTIMIZATION ON,ALL}{$ENDIF}
{$ELSEIFDEF Windows} {$APPTYPE CONSOLE}{$ENDIF}
{$ENDIF}
uses
SysUtils,primTrialprimsieve;
var
p,sum : NativeInt;
begin
sum := actPrime0;
p := 0;
repeat inc(sum,p); p := NextPrime until p >= 2*1000*1000;
repeat inc(sum,p);p := Nextprime until p >= 2*1000*1000;
writeln(sum);
{$IFDEF WINDOWS} readln;{$ENDIF}
end.</langsyntaxhighlight>
{{out}}
<pre>
142913828922</pre>
 
=={{header|Perl}}==
<syntaxhighlight 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";</syntaxhighlight>
{{out}}
<pre>
142913828922
</pre>
 
=={{header|Phix}}==
<!--<syntaxhighlight lang="phix">(phixonline)-->
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"The sum of primes below 2 million is %,d\n"</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">sum</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">get_primes_le</span><span style="color: #0000FF;">(</span><span style="color: #000000;">2e6</span><span style="color: #0000FF;">)))</span>
<!--</syntaxhighlight>-->
{{out}}
<pre>
The sum of primes below 2 million is 142,913,828,922
</pre>
 
 
=={{header|Python}}==
===Procedural===
<syntaxhighlight 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)</syntaxhighlight>
{{out}}
<pre>142913828922</pre>
 
===Functional===
<syntaxhighlight 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()</syntaxhighlight>
{{Out}}
<pre>142913828922</pre>
 
 
Or, more efficiently, assuming that we have a generator of primes:
 
<syntaxhighlight 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()</syntaxhighlight>
{{Out}}
<pre>142913828922</pre>
 
=={{header|Quackery}}==
 
<code>eratosthenes</code> and <code>isprime</code> are defined at[[Sieve of Eratosthenes#Quackery]].
 
<syntaxhighlight lang="Quackery"> 2000000 eratosthenes
0 2000000 times [ i isprime if [ i + ] ] echo
</syntaxhighlight>
 
{{out}}
 
<pre>142913828922</pre>
 
=={{header|Raku}}==
Slow, but only using compiler built-ins (about 5 seconds)
<syntaxhighlight lang="raku" perl6line>say sum (^2e6).grep: {.&is-prime};</langsyntaxhighlight>
{{out}}
<pre>142913828922</pre>
 
Much faster using external libraries (well under half a second)
<syntaxhighlight lang="raku" perl6line>use Math::Primesieve;
my $sieve = Math::Primesieve.new;
say sum $sieve.primes(2e6.Int);</langsyntaxhighlight>
Same output
 
=={{header|Ring}}==
<langsyntaxhighlight lang="ring">
load "stdlib.ring"
see "working..." + nl
Line 192 ⟶ 741:
see "" + sum + nl
see "done..." + nl
</syntaxhighlight>
</lang>
{{out}}
<pre>
Line 199 ⟶ 748:
142,913,828,922
done...
</pre>
 
=={{header|RPL}}==
{{works with|HP|49}}
≪ 0 1
'''WHILE''' NEXTPRIME DUP 2E6 <
'''REPEAT''' SWAP OVER + SWAP
'''END''' DROP
≫ '<span style="color:blue">TASK</span>' STO
{{out}}
<pre>
1: 142913828922
</pre>
 
=={{header|Ruby}}==
<syntaxhighlight lang="ruby">puts Prime.each(2_000_000).sum</syntaxhighlight>
{{out}}
<pre>142913828922
</pre>
 
=={{header|Rust}}==
<syntaxhighlight lang="Rust">use primes::is_prime ;
 
fn main() {
println!("{}" , (2u64..2000000u64).filter( | &d | is_prime( d )).sum::<u64>() ) ;
}</syntaxhighlight>
{{out}}
<pre>
142913828922
</pre>
 
=={{header|Sidef}}==
 
Built-in:
<syntaxhighlight lang="ruby">say sum_primes(2e6) #=> 142913828922</syntaxhighlight>
 
Linear algorithm:
<syntaxhighlight lang="ruby">func sum_primes(limit) {
var sum = 0
for (var p = 2; p < limit; p.next_prime!) {
sum += p
}
return sum
}
 
say sum_primes(2e6)</syntaxhighlight>
 
Sublinear algorithm:
<syntaxhighlight lang="ruby">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)</syntaxhighlight>
{{out}}
<pre>
142913828922
</pre>
 
Line 204 ⟶ 828:
{{libheader|Wren-math}}
{{libheader|Wren-fmt}}
<langsyntaxhighlight ecmascriptlang="wren">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)))</langsyntaxhighlight>
 
{{out}}
Line 213 ⟶ 837:
The sum of all primes below 2 million is 142,913,828,922.
</pre>
 
=={{header|XPL0}}==
Takes 3.7 seconds on Pi4.
<syntaxhighlight 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);
]</syntaxhighlight>
 
{{out}}
<pre>
142913828922
</pre>
 
=={{header|Yabasic}}==
{{trans|Python}}
<syntaxhighlight 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")</syntaxhighlight>
Ulrie
258

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/317204...363728"