Summation of primes: Difference between revisions
Content added Content deleted
(→{{header|Sidef}}: added a sublinear version) |
Thundergnat (talk | contribs) m (syntax highlighting fixup automation) |
||
Line 9: | Line 9: | ||
=={{header|ALGOL 68}}== |
=={{header|ALGOL 68}}== |
||
{{libheader|ALGOL 68-primes}} |
{{libheader|ALGOL 68-primes}} |
||
< |
<syntaxhighlight lang="algol68">BEGIN # sum primes up to 2 000 000 # |
||
PR read "primes.incl.a68" PR |
PR read "primes.incl.a68" PR |
||
# return s space-separated into groups of 3 digits # |
# return s space-separated into groups of 3 digits # |
||
Line 33: | Line 33: | ||
OD; |
OD; |
||
print( ( space separate( whole( sum, 0 ) ), newline ) ) |
print( ( space separate( whole( sum, 0 ) ), newline ) ) |
||
END</ |
END</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 43: | Line 43: | ||
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)! |
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 < 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 |
if ((n mod 2 = 0) or (n mod 3 = 0) or (n mod 5 = 0)) then return false |
||
Line 67: | Line 67: | ||
end sumPrimes |
end sumPrimes |
||
sumPrimes below 2000000</ |
sumPrimes below 2000000</syntaxhighlight> |
||
{{output}} |
{{output}} |
||
<lang |
<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: |
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 |
set limit to this - 1 |
||
-- Is the limit 2 or lower? |
-- Is the limit 2 or lower? |
||
Line 124: | Line 124: | ||
end sumPrimes |
end sumPrimes |
||
sumPrimes below 2000000</ |
sumPrimes below 2000000</syntaxhighlight> |
||
=={{header|AWK}}== |
=={{header|AWK}}== |
||
<syntaxhighlight lang="awk"> |
|||
<lang AWK> |
|||
# syntax: GAWK -f SUMMATION_OF_PRIMES.AWK |
# syntax: GAWK -f SUMMATION_OF_PRIMES.AWK |
||
BEGIN { |
BEGIN { |
||
Line 161: | Line 161: | ||
return(1) |
return(1) |
||
} |
} |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 170: | Line 170: | ||
=={{header|BASIC}}== |
=={{header|BASIC}}== |
||
==={{header|FreeBASIC}}=== |
==={{header|FreeBASIC}}=== |
||
< |
<syntaxhighlight lang="freebasic">#include "isprime.bas" |
||
dim as integer sum = 2, i, n=1 |
dim as integer sum = 2, i, n=1 |
||
Line 180: | Line 180: | ||
next i |
next i |
||
print sum</ |
print sum</syntaxhighlight> |
||
{{out}}<pre>142913828922</pre> |
{{out}}<pre>142913828922</pre> |
||
==={{header|GW-BASIC}}=== |
==={{header|GW-BASIC}}=== |
||
< |
<syntaxhighlight lang="gwbasic">10 S# = 2 |
||
20 FOR P = 3 TO 1999999! STEP 2 |
20 FOR P = 3 TO 1999999! STEP 2 |
||
30 GOSUB 80 |
30 GOSUB 80 |
||
Line 199: | Line 199: | ||
140 Q = 1 |
140 Q = 1 |
||
150 RETURN |
150 RETURN |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}}<pre>142913828922</pre> |
{{out}}<pre>142913828922</pre> |
||
=={{header|C}}== |
=={{header|C}}== |
||
< |
<syntaxhighlight lang="c">#include<stdio.h> |
||
#include<stdlib.h> |
#include<stdlib.h> |
||
Line 224: | Line 224: | ||
printf( "%ld\n", s ); |
printf( "%ld\n", s ); |
||
return 0; |
return 0; |
||
}</ |
}</syntaxhighlight> |
||
{{out}}<pre>142913828922</pre> |
{{out}}<pre>142913828922</pre> |
||
=={{header|CLU}}== |
=={{header|CLU}}== |
||
< |
<syntaxhighlight lang="clu">isqrt = proc (s: int) returns (int) |
||
x0: int := s/2 |
x0: int := s/2 |
||
if x0=0 then |
if x0=0 then |
||
Line 263: | Line 263: | ||
start_up = proc () |
start_up = proc () |
||
stream$putl(stream$primary_output(), int$unparse(sum_primes_to(2000000))) |
stream$putl(stream$primary_output(), int$unparse(sum_primes_to(2000000))) |
||
end start_up </ |
end start_up </syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>142913828922</pre> |
<pre>142913828922</pre> |
||
=={{header|Crystal}}== |
=={{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 |
return false unless (n | 1 == 3 if n < 5) || (n % 6) | 4 == 5 |
||
sqrt = Math.isqrt(n) |
sqrt = Math.isqrt(n) |
||
Line 285: | Line 285: | ||
puts "The sum of all primes below 2 million is #{(0i64..2000000i64).sum { |n| prime?(n) ? n : 0u64 }}" |
puts "The sum of all primes below 2 million is #{(0i64..2000000i64).sum { |n| prime?(n) ? n : 0u64 }}" |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre>The sum of all primes below 2 million is 142913828923. |
<pre>The sum of all primes below 2 million is 142913828923. |
||
Line 292: | Line 292: | ||
=={{header|F_Sharp|F#}}== |
=={{header|F_Sharp|F#}}== |
||
This task uses [http://www.rosettacode.org/wiki/Extensible_prime_generator#The_functions Extensible Prime Generator (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 |
// Summation of primes. Nigel Galloway: November 9th., 2021 |
||
printfn $"%d{primes64()|>Seq.takeWhile((>)2000000L)|>Seq.sum}" |
printfn $"%d{primes64()|>Seq.takeWhile((>)2000000L)|>Seq.sum}" |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 302: | Line 302: | ||
=={{header|Factor}}== |
=={{header|Factor}}== |
||
< |
<syntaxhighlight lang="factor">USING: math.primes prettyprint sequences ; |
||
2,000,000 primes-upto sum .</ |
2,000,000 primes-upto sum .</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 311: | Line 311: | ||
=={{header|Fermat}}== |
=={{header|Fermat}}== |
||
< |
<syntaxhighlight lang="fermat">s:=2; |
||
for p=3 to 1999999 by 2 do if Isprime(p) then s:=s+p fi od; |
for p=3 to 1999999 by 2 do if Isprime(p) then s:=s+p fi od; |
||
!!s;</ |
!!s;</syntaxhighlight> |
||
{{out}}<pre>142913828922</pre> |
{{out}}<pre>142913828922</pre> |
||
=={{header|Go}}== |
=={{header|Go}}== |
||
{{libheader|Go-rcu}} |
{{libheader|Go-rcu}} |
||
< |
<syntaxhighlight lang="go">package main |
||
import ( |
import ( |
||
Line 331: | Line 331: | ||
} |
} |
||
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 340: | Line 340: | ||
=={{header|Haskell}}== |
=={{header|Haskell}}== |
||
< |
<syntaxhighlight lang="haskell">import Data.Numbers.Primes (primes) |
||
sumOfPrimesBelow :: Integral a => a -> a |
sumOfPrimesBelow :: Integral a => a -> a |
||
Line 347: | Line 347: | ||
main :: IO () |
main :: IO () |
||
main = print $ sumOfPrimesBelow 2000000</ |
main = print $ sumOfPrimesBelow 2000000</syntaxhighlight> |
||
{{Out}} |
{{Out}} |
||
<pre>142913828922</pre> |
<pre>142913828922</pre> |
||
Line 357: | Line 357: | ||
See [[Erd%C5%91s-primes#jq]] for a suitable definition of `is_prime/1` as used here. |
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))</ |
sum(2, range(3 ; 2E6; 2) | select(is_prime))</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 366: | Line 366: | ||
=={{header|Julia}}== |
=={{header|Julia}}== |
||
< |
<syntaxhighlight lang="julia">using Primes |
||
@show sum(primes(2_000_000)) # sum(primes(2000000)) = 142913828922 |
@show sum(primes(2_000_000)) # sum(primes(2000000)) = 142913828922 |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header|Mathematica}} / {{header|Wolfram Language}}== |
=={{header|Mathematica}} / {{header|Wolfram Language}}== |
||
< |
<syntaxhighlight lang="mathematica">Total[Most@NestWhileList[NextPrime, 2, # < 2000000 &]]</syntaxhighlight> |
||
{{out}}<pre> |
{{out}}<pre> |
||
Line 378: | Line 378: | ||
=={{header|PARI/GP}}== |
=={{header|PARI/GP}}== |
||
< |
<syntaxhighlight lang="parigp"> |
||
s=2; p=3 |
s=2; p=3 |
||
while(p<2000000,if(isprime(p),s=s+p);p=p+2) |
while(p<2000000,if(isprime(p),s=s+p);p=p+2) |
||
print(s) |
print(s) |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}}<pre> |
{{out}}<pre> |
||
142913828922 |
142913828922 |
||
Line 388: | Line 388: | ||
=={{header|Pascal}}== |
=={{header|Pascal}}== |
||
uses {{libheader|primTrial}} |
uses {{libheader|primTrial}} |
||
< |
<syntaxhighlight lang="pascal"> |
||
program SumPrimes; |
program SumPrimes; |
||
{$IFDEF FPC}{$MODE DELPHI}{$OPTIMIZATION ON,ALL} |
{$IFDEF FPC}{$MODE DELPHI}{$OPTIMIZATION ON,ALL} |
||
Line 402: | Line 402: | ||
writeln(sum); |
writeln(sum); |
||
{$IFDEF WINDOWS} readln;{$ENDIF} |
{$IFDEF WINDOWS} readln;{$ENDIF} |
||
end.</ |
end.</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 408: | Line 408: | ||
=={{header|Perl}}== |
=={{header|Perl}}== |
||
< |
<syntaxhighlight lang="perl">#!/usr/bin/perl |
||
use strict; # https://rosettacode.org/wiki/Summation_of_primes |
use strict; # https://rosettacode.org/wiki/Summation_of_primes |
||
Line 415: | Line 415: | ||
use List::Util qw( sum ); |
use List::Util qw( sum ); |
||
print sum( @{ primes( 2e6 ) } ), "\n";</ |
print sum( @{ primes( 2e6 ) } ), "\n";</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 422: | Line 422: | ||
=={{header|Phix}}== |
=={{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> |
<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}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 433: | Line 433: | ||
=={{header|Python}}== |
=={{header|Python}}== |
||
===Procedural=== |
===Procedural=== |
||
< |
<syntaxhighlight lang="python">#!/usr/bin/python |
||
def isPrime(n): |
def isPrime(n): |
||
Line 448: | Line 448: | ||
suma += i |
suma += i |
||
n+=1 |
n+=1 |
||
print(suma)</ |
print(suma)</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>142913828922</pre> |
<pre>142913828922</pre> |
||
===Functional=== |
===Functional=== |
||
< |
<syntaxhighlight lang="python">'''Summatiom of primes''' |
||
from functools import reduce |
from functools import reduce |
||
Line 497: | Line 497: | ||
# MAIN --- |
# MAIN --- |
||
if __name__ == '__main__': |
if __name__ == '__main__': |
||
main()</ |
main()</syntaxhighlight> |
||
{{Out}} |
{{Out}} |
||
<pre>142913828922</pre> |
<pre>142913828922</pre> |
||
Line 504: | Line 504: | ||
Or, more efficiently, assuming that we have a generator of primes: |
Or, more efficiently, assuming that we have a generator of primes: |
||
< |
<syntaxhighlight lang="python">'''Summatiom of primes''' |
||
from itertools import count, takewhile |
from itertools import count, takewhile |
||
Line 568: | Line 568: | ||
# MAIN --- |
# MAIN --- |
||
if __name__ == '__main__': |
if __name__ == '__main__': |
||
main()</ |
main()</syntaxhighlight> |
||
{{Out}} |
{{Out}} |
||
<pre>142913828922</pre> |
<pre>142913828922</pre> |
||
Line 574: | Line 574: | ||
=={{header|Raku}}== |
=={{header|Raku}}== |
||
Slow, but only using compiler built-ins (about 5 seconds) |
Slow, but only using compiler built-ins (about 5 seconds) |
||
<lang |
<syntaxhighlight lang="raku" line>say sum (^2e6).grep: {.&is-prime};</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>142913828922</pre> |
<pre>142913828922</pre> |
||
Much faster using external libraries (well under half a second) |
Much faster using external libraries (well under half a second) |
||
<lang |
<syntaxhighlight lang="raku" line>use Math::Primesieve; |
||
my $sieve = Math::Primesieve.new; |
my $sieve = Math::Primesieve.new; |
||
say sum $sieve.primes(2e6.Int);</ |
say sum $sieve.primes(2e6.Int);</syntaxhighlight> |
||
Same output |
Same output |
||
=={{header|Ring}}== |
=={{header|Ring}}== |
||
< |
<syntaxhighlight lang="ring"> |
||
load "stdlib.ring" |
load "stdlib.ring" |
||
see "working..." + nl |
see "working..." + nl |
||
Line 600: | Line 600: | ||
see "" + sum + nl |
see "" + sum + nl |
||
see "done..." + nl |
see "done..." + nl |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 610: | Line 610: | ||
=={{header|Ruby}}== |
=={{header|Ruby}}== |
||
<lang |
<syntaxhighlight lang="ruby">puts Prime.each(2_000_000).sum</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>142913828922 |
<pre>142913828922 |
||
Line 618: | Line 618: | ||
Built-in: |
Built-in: |
||
< |
<syntaxhighlight lang="ruby">say sum_primes(2e6) #=> 142913828922</syntaxhighlight> |
||
Linear algorithm: |
Linear algorithm: |
||
< |
<syntaxhighlight lang="ruby">func sum_primes(limit) { |
||
var sum = 0 |
var sum = 0 |
||
for (var p = 2; p < limit; p.next_prime!) { |
for (var p = 2; p < limit; p.next_prime!) { |
||
Line 629: | Line 629: | ||
} |
} |
||
say sum_primes(2e6)</ |
say sum_primes(2e6)</syntaxhighlight> |
||
Sublinear algorithm: |
Sublinear algorithm: |
||
< |
<syntaxhighlight lang="ruby">func sum_of_primes(n) { |
||
return 0 if (n <= 1) |
return 0 if (n <= 1) |
||
Line 655: | Line 655: | ||
} |
} |
||
say sum_of_primes(2e6)</ |
say sum_of_primes(2e6)</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 664: | Line 664: | ||
{{libheader|Wren-math}} |
{{libheader|Wren-math}} |
||
{{libheader|Wren-fmt}} |
{{libheader|Wren-fmt}} |
||
< |
<syntaxhighlight lang="ecmascript">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 676: | Line 676: | ||
=={{header|XPL0}}== |
=={{header|XPL0}}== |
||
Takes 3.7 seconds on Pi4. |
Takes 3.7 seconds on Pi4. |
||
< |
<syntaxhighlight lang="xpl0">func IsPrime(N); \Return 'true' if N is a prime number >= 3 |
||
int N, I; |
int N, I; |
||
[if (N&1) = 0 then return false; \N is even |
[if (N&1) = 0 then return false; \N is even |
||
Line 693: | Line 693: | ||
Format(1, 0); \don't show places after decimal point |
Format(1, 0); \don't show places after decimal point |
||
RlOut(0, Sum); |
RlOut(0, Sum); |
||
]</ |
]</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 702: | Line 702: | ||
=={{header|Yabasic}}== |
=={{header|Yabasic}}== |
||
{{trans|Python}} |
{{trans|Python}} |
||
< |
<syntaxhighlight lang="yabasic">// Rosetta Code problem: http://rosettacode.org/wiki/Summation_of_primes |
||
// by Galileo, 04/2022 |
// by Galileo, 04/2022 |
||
Line 718: | Line 718: | ||
if isPrime(i) suma = suma + i |
if isPrime(i) suma = suma + i |
||
next |
next |
||
print str$(suma, "%12.f")</ |
print str$(suma, "%12.f")</syntaxhighlight> |