Summation of primes: Difference between revisions
(Added Go) |
No edit summary |
||
(53 intermediate revisions by 32 users not shown) | |||
Line 2: | Line 2: | ||
;Task: |
;Task: |
||
<br>The task |
<br>The task description is taken from Project Euler (https://projecteuler.net/problem=10) |
||
<br>The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17 |
<br>The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17 |
||
<br>Find the sum of all the primes below '''two million''' |
<br>Find the sum of all the primes below '''two million''' |
||
<br><br> |
<br><br> |
||
=={{header|ALGOL 68}}== |
|||
{{libheader|ALGOL 68-primes}} |
|||
<syntaxhighlight 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</syntaxhighlight> |
|||
{{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}}=== |
|||
<syntaxhighlight 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</syntaxhighlight> |
|||
{{out}}<pre>142913828922</pre> |
|||
==={{header|GW-BASIC}}=== |
|||
<syntaxhighlight 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 |
|||
</syntaxhighlight> |
|||
{{out}}<pre>142913828922</pre> |
|||
=={{header|C}}== |
|||
<syntaxhighlight 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; |
|||
}</syntaxhighlight> |
|||
{{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}}== |
|||
<syntaxhighlight lang="fermat">s:=2; |
|||
for p=3 to 1999999 by 2 do if Isprime(p) then s:=s+p fi od; |
|||
!!s;</syntaxhighlight> |
|||
{{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}}== |
=={{header|Go}}== |
||
{{libheader|Go-rcu}} |
{{libheader|Go-rcu}} |
||
< |
<syntaxhighlight lang="go">package main |
||
import ( |
import ( |
||
Line 22: | Line 407: | ||
} |
} |
||
fmt.Printf("The sum of all primes below 2 million is %s.\n", rcu.Commatize(sum)) |
fmt.Printf("The sum of all primes below 2 million is %s.\n", rcu.Commatize(sum)) |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 28: | Line 413: | ||
The sum of all primes below 2 million is 142,913,828,922. |
The sum of all primes below 2 million is 142,913,828,922. |
||
</pre> |
</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}}== |
|||
<syntaxhighlight lang="julia">using Primes |
|||
@show sum(primes(2_000_000)) # sum(primes(2000000)) = 142913828922 |
|||
</syntaxhighlight> |
|||
=={{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}}== |
|||
<syntaxhighlight lang="parigp"> |
|||
s=2; p=3 |
|||
while(p<2000000,if(isprime(p),s=s+p);p=p+2) |
|||
print(s) |
|||
</syntaxhighlight> |
|||
{{out}}<pre> |
|||
142913828922 |
|||
</pre> |
|||
=={{header|Pascal}}== |
|||
uses {{libheader|primsieve}} [[Extensible_prime_generator#Pascal|Extensible_prime_generator]] |
|||
<syntaxhighlight lang="pascal"> |
|||
program SumPrimes; |
|||
{$IFDEF FPC}{$MODE DELPHI}{$OPTIMIZATION ON,ALL}{$ENDIF} |
|||
{$IFDEF Windows}{$APPTYPE CONSOLE}{$ENDIF} |
|||
uses |
|||
SysUtils,primsieve; |
|||
var |
|||
p,sum : NativeInt; |
|||
begin |
|||
sum := 0; |
|||
p := 0; |
|||
repeat inc(sum,p);p := Nextprime until p >= 2*1000*1000; |
|||
writeln(sum); |
|||
{$IFDEF WINDOWS} readln;{$ENDIF} |
|||
end.</syntaxhighlight> |
|||
{{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" line>say sum (^2e6).grep: {.&is-prime};</syntaxhighlight> |
|||
{{out}} |
|||
<pre>142913828922</pre> |
|||
Much faster using external libraries (well under half a second) |
|||
<syntaxhighlight lang="raku" line>use Math::Primesieve; |
|||
my $sieve = Math::Primesieve.new; |
|||
say sum $sieve.primes(2e6.Int);</syntaxhighlight> |
|||
Same output |
|||
=={{header|Ring}}== |
=={{header|Ring}}== |
||
< |
<syntaxhighlight lang="ring"> |
||
load "stdlib.ring" |
load "stdlib.ring" |
||
see "working..." + nl |
see "working..." + nl |
||
sum = |
sum = 2 |
||
limit = 2000000 |
limit = 2000000 |
||
for n = |
for n = 3 to limit step 2 |
||
if isprime(n) |
if isprime(n) |
||
sum += n |
sum += n |
||
Line 45: | Line 741: | ||
see "" + sum + nl |
see "" + sum + nl |
||
see "done..." + nl |
see "done..." + nl |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 52: | Line 748: | ||
142,913,828,922 |
142,913,828,922 |
||
done... |
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> |
</pre> |
||
Line 57: | Line 828: | ||
{{libheader|Wren-math}} |
{{libheader|Wren-math}} |
||
{{libheader|Wren-fmt}} |
{{libheader|Wren-fmt}} |
||
< |
<syntaxhighlight lang="wren">import "./math" for Int, Nums |
||
import "./fmt" for Fmt |
import "./fmt" for Fmt |
||
Fmt.print("The sum of all primes below 2 million is $,d.", Nums.sum(Int.primeSieve(2e6-1)))</ |
Fmt.print("The sum of all primes below 2 million is $,d.", Nums.sum(Int.primeSieve(2e6-1)))</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 66: | Line 837: | ||
The sum of all primes below 2 million is 142,913,828,922. |
The sum of all primes below 2 million is 142,913,828,922. |
||
</pre> |
</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> |
Latest revision as of 15:59, 16 April 2024
- 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
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
Arturo
print sum select 2..2000000 => prime?
- Output:
142913828922
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.
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;
- Output:
Sum of Primes Below 2 million: 142,913,828,922 Elapsed Time: 17.405 ms.
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
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
- Output:
142913828922
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))
}
- 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
J
+/p: i. p:inv 2e6
142913828922
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...
p:inv 2e6
148933
p: p:inv 2e6
2000003
Also, i. n
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): +/
sums a list (evaluates the hypothetical expression which would result from insert +
between each element of that list).
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
Maxima
block(primes(2,2000000),apply("+",%%));
Output
/* 142913828922 */
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
- 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
program SumPrimes;
{$IFDEF FPC}{$MODE DELPHI}{$OPTIMIZATION ON,ALL}{$ENDIF}
{$IFDEF Windows}{$APPTYPE CONSOLE}{$ENDIF}
uses
SysUtils,primsieve;
var
p,sum : NativeInt;
begin
sum := 0;
p := 0;
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...
RPL
≪ 0 1
WHILE NEXTPRIME DUP 2E6 <
REPEAT SWAP OVER + SWAP
END DROP
≫ 'TASK' STO
- Output:
1: 142913828922
Ruby
puts Prime.each(2_000_000).sum
- Output:
142913828922
Rust
use primes::is_prime ;
fn main() {
println!("{}" , (2u64..2000000u64).filter( | &d | is_prime( d )).sum::<u64>() ) ;
}
- 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
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
// 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")
- Draft Programming Tasks
- ALGOL 68
- ALGOL 68-primes
- AppleScript
- Arturo
- AWK
- BASIC
- FreeBASIC
- GW-BASIC
- C
- CLU
- Crystal
- Delphi
- SysUtils,StdCtrls
- F Sharp
- Factor
- Fermat
- FutureBasic
- Go
- Go-rcu
- Haskell
- J
- Jq
- Julia
- Mathematica
- Wolfram Language
- Maxima
- Nim
- PARI/GP
- Pascal
- Primsieve
- Perl
- Phix
- Python
- Quackery
- Raku
- Ring
- RPL
- Ruby
- Rust
- Sidef
- Wren
- Wren-math
- Wren-fmt
- XPL0
- Yabasic