The sieve of Sundaram: Difference between revisions

Line 27:

<~~lang~~ 11l>F sieve_of_Sundaram(nth, print_all = 1B)

<syntaxhighlight lang="11l">F sieve_of_Sundaram(nth, print_all = 1B)

‘

The sieve of Sundaram is a simple deterministic algorithm for finding all the

Line 57:

sieve_of_Sundaram(100, 1B)

sieve_of_Sundaram(1000000, 0B)</~~lang~~>

sieve_of_Sundaram(1000000, 0B)</syntaxhighlight>

Line 82:

To run this with Algol 68G, you will need to increase the heap size by specifying e.g. <code>-heap=64M</code> on the command line.

<~~lang~~ algol68>BEGIN # sieve of Sundaram #

<syntaxhighlight lang="algol68">BEGIN # sieve of Sundaram #

INT n = 8 000 000;

INT none = 0, mark1 = 1, mark2 = 2;

Line 124:

print( ( "The millionth Sundaram prime is ", whole( last, 0 ), newline ) )

FI

END</~~lang~~>

END</syntaxhighlight>

<pre>

Line 144:

The "nth prime" calculation here's gleaned from the Python and Julia solutions and the limitations to marking partly from the Phix.

<~~lang~~ applescript>on sieveOfSundaram(indexRange)

<syntaxhighlight lang="applescript">on sieveOfSundaram(indexRange)

if (indexRange's class is list) then

set n1 to beginning of indexRange

Line 230:

end task

task()</~~lang~~>

task()</syntaxhighlight>

<~~lang~~ applescript>"1st to 100th Sundaram primes:

<syntaxhighlight lang="applescript">"1st to 100th Sundaram primes:

3 5 7 11 13 17 19 23 29 31

37 41 43 47 53 59 61 67 71 73

Line 245:

479 487 491 499 503 509 521 523 541 547

1,000,000th:

15485867"</~~lang~~>

15485867"</syntaxhighlight>

=={{header|C}}==

#include <stdio.h>

#include <stdlib.h>

Line 278:

}

</syntaxhighlight>

</lang>

<pre>

Line 298:

<strike>Generating prime numbers during sieve creation gives a performance boost over completing the sieve and then scanning the sieve for output. There are, of course, a few at the end to scan out.</strike>

Heh, nope. It's faster to do the sieving first, then the generation afterwards.

<~~lang~~ csharp>using System;

<syntaxhighlight lang="csharp">using System;

using System.Collections.Generic;

using System.Linq;

Line 340:

yield return (v << 1) + 1;

}

}</~~lang~~>

}</syntaxhighlight>

Under <strike>1/5</strike> 1/8 of a second @ Tio.run

Line 359:

=={{header|F_Sharp|F#}}==

<~~lang~~ fsharp>

// The sieve of Sundaram. Nigel Galloway: August 7th., 2021

let sPrimes()=

Line 372:

sPrimes()|>Seq.take 100|>Seq.iter(printf "%d "); printfn ""

printfn "The millionth Sundaram prime is %d" (Seq.item 999999 (sPrimes()))

</syntaxhighlight>

</lang>

<pre>

Line 380:

=={{header|Fortran}}==

PROGRAM SUNDARAM

IMPLICIT NONE

Line 436:

END PROGRAM SUNDARAM

</syntaxhighlight>

</lang>

<pre>

Line 457:

<~~lang~~ go>package main

<syntaxhighlight lang="go">package main

import (

Line 541:

fmt.Printf("\nUsing the Sieve of Eratosthenes would have generated them in %s ms.\n", celapsed)

fmt.Printf("\nAs a check, the %s Sundaram prime would again have been %s\n", million, millionth)

}</~~lang~~>

}</syntaxhighlight>

Line 567:

=={{header|Haskell}}==

<~~lang~~ haskell>import Data.List (intercalate, transpose)

<syntaxhighlight lang="haskell">import Data.List (intercalate, transpose)

import Data.List.Split (chunksOf)

import qualified Data.Set as S

Line 609:

let ws = maximum . fmap length <$> transpose rows

pw = printf . flip intercalate ["%", "s"] . show

in unlines $ intercalate gap . zipWith pw ws <$> rows</~~lang~~>

in unlines $ intercalate gap . zipWith pw ws <$> rows</syntaxhighlight>

<pre>First 100 Sundaram primes (starting at 3):

Line 625:

=={{header|JavaScript}}==

<~~lang~~ javascript>(() => {

<syntaxhighlight lang="javascript">(() => {

"use strict";

Line 732:

return main();

})();</~~lang~~>

})();</syntaxhighlight>

<pre>First 100 Sundaram primes

Line 758:

(*) For large sieves, gojq will consume a very large amount of memory.

<~~lang~~ jq># `sieve_of_Sundaram` as defined here generates the stream of

<syntaxhighlight lang="jq"># `sieve_of_Sundaram` as defined here generates the stream of

# consecutive primes from 3 on but less than or equal to the specified

# limit specified by `.`.

Line 795:

elif $n <= 100 then ($n | 1.2 * . * log) | sieve

else $n | (1.15 * . * log) | sieve # OK

end;</~~lang~~>

end;</syntaxhighlight>

'''For pretty-printing'''

<~~lang~~ jq>def lpad($len): tostring | ($len - length) as $l | (" " * $l)[:$l] + .;

<syntaxhighlight lang="jq">def lpad($len): tostring | ($len - length) as $l | (" " * $l)[:$l] + .;

def nwise($n):

def n: if length <= $n then . else .[0:$n] , (.[$n:] | n) end;

n;</~~lang~~>

n;</syntaxhighlight>

'''The Tasks'''

<~~lang~~ jq>def hundred:

<syntaxhighlight lang="jq">def hundred:

Sundaram_primes(100)

| nwise(10)

Line 810:

"First hundred:", hundred,

"\nMillionth is \(Sundaram_primes(1000000)[-1])"</~~lang~~>

"\nMillionth is \(Sundaram_primes(1000000)[-1])"</syntaxhighlight>

<pre>

Line 831:

=={{header|Julia}}==

<~~lang~~ julia>

"""

The sieve of Sundaram is a simple deterministic algorithm for finding all the

Line 870:

using Primes; @show count(primesmask(15485867))

@time count(primesmask(15485867))

</~~lang~~>{{out}}

</syntaxhighlight>{{out}}

<pre>

3 5 7 11 13 17 19 23 29 31

Line 894:

=={{header|Mathematica}}/{{header|Wolfram Language}}==

<~~lang~~ ~~Mathematica~~>ClearAll[SieveOfSundaram]

<syntaxhighlight lang="mathematica">ClearAll[SieveOfSundaram]

SieveOfSundaram[n_Integer] := Module[{i, prefac, k, ints},

k = Floor[(n - 2)/2];

Line 909:

]

SieveOfSundaram[600][[;; 100]]

SieveOfSundaram[16000000][[10^6]]</~~lang~~>

SieveOfSundaram[16000000][[10^6]]</syntaxhighlight>

<pre>{3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199,211,223,227,229,233,239,241,251,257,263,269,271,277,281,283,293,307,311,313,317,331,337,347,349,353,359,367,373,379,383,389,397,401,409,419,421,431,433,439,443,449,457,461,463,467,479,487,491,499,503,509,521,523,541,547}

Line 915:

=={{header|Nim}}==

<~~lang~~ ~~Nim~~>import strutils

<syntaxhighlight lang="nim">import strutils

const N = 8_000_000

Line 957:

if last == 0:

quit "Not enough values in sieve. Found only $#.".format(count), QuitFailure

echo "The millionth Sundaram prime is ", ($last).insertSep()</~~lang~~>

echo "The millionth Sundaram prime is ", ($last).insertSep()</syntaxhighlight>

Line 975:

=={{header|Perl}}==

<~~lang~~ perl>use strict;

<syntaxhighlight lang="perl">use strict;

use warnings;

use feature 'say';

Line 1,002:

(say "One millionth: " . (1+2*$index)) and last if $count == $nth;

++$index;

}</~~lang~~>

}</syntaxhighlight>

<pre>First 100 Sundaram primes:

Line 1,019:

=={{header|Phix}}==

with javascript_semantics

function sos(integer n)

Line 1,046:

printf(1,"The first 100 odd prime numbers:\n%s\n",{join_by(apply(true,sprintf,{{"%3d"},s[1..100]}),1,10)})

printf(1,"The millionth odd prime number: %,d\n",{s[1_000_000]})

<pre>

Line 1,066:

=={{header|Python}}==

===Python :: Procedural===

<~~lang~~ python>from numpy import log

<syntaxhighlight lang="python">from numpy import log

def sieve_of_Sundaram(nth, print_all=True):

Line 1,101:

sieve_of_Sundaram(1000000, False)

</~~lang~~>{{out}}

</syntaxhighlight>{{out}}

<pre>

3 5 7 11 13 17 19 23 29 31

Line 1,121:

===Python :: Functional===

Composing functionally, and obtaining slightly better performance by defining a set (rather than list) of exclusions.

<~~lang~~ python>'''Sieve of Sundaram'''

<syntaxhighlight lang="python">'''Sieve of Sundaram'''

from math import floor, log, sqrt

Line 1,205:

# MAIN ---

if __name__ == '__main__':

main()</~~lang~~>

main()</syntaxhighlight>

<pre>First hundred Sundaram primes, starting at 3:

Line 1,229:

<~~lang~~ racket>#lang racket

<syntaxhighlight lang="racket">#lang racket

(define (make-sieve-as-set limit)

Line 1,254:

(module+ main

(Sieve-of-Sundaram))</~~lang~~>

(Sieve-of-Sundaram))</syntaxhighlight>

Line 1,262:

=={{header|Raku}}==

<lang ~~perl6~~>my $nth = 1_000_000;

<syntaxhighlight lang="raku" line>my $nth = 1_000_000;

my $k = Int.new: 2.4 * $nth * log($nth) / 2;

Line 1,289:

say $index * 2 + 1 and last if $count == $nth;

++$index;

}</~~lang~~>

}</syntaxhighlight>

<pre>First 100 Sundaram primes:

Line 1,309:

=={{header|REXX}}==

For the calculation of the  1,000,000th  Sundaram prime,   it requires a 64-bit version of REXX.

<~~lang~~ rexx>/*REXX program finds & displays N Sundaram primes, or displays the Nth Sundaram prime.*/

<syntaxhighlight lang="rexx">/*REXX program finds & displays N Sundaram primes, or displays the Nth Sundaram prime.*/

parse arg n cols . /*get optional number of primes to find*/

if n=='' | n=="," then n= 100 /*Not specified? Then assume default.*/

Line 1,341:

exit 0 /*stick a fork in it, we're all done. */

/*──────────────────────────────────────────────────────────────────────────────────────*/

commas: parse arg ?; do jc=length(?)-3 to 1 by -3; ?=insert(',', ?, jc); end; return ?</~~lang~~>

commas: parse arg ?; do jc=length(?)-3 to 1 by -3; ?=insert(',', ?, jc); end; return ?</syntaxhighlight>

<pre>

Line 1,367:

=={{header|Ruby}}==

Based on the Python code from the Wikipedia lemma.

<~~lang~~ ruby>def sieve_of_sundaram(upto)

<syntaxhighlight lang="ruby">def sieve_of_sundaram(upto)

n = (2.4 * upto * Math.log(upto)) / 2

k = (n - 3) / 2 + 1

Line 1,382:

n = 1_000_000

puts "\nThe #{n}th sundaram prime is #{sieve_of_sundaram(n)[n-1]}"

</syntaxhighlight>

</lang>

<pre>[3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547]

Line 1,392:

I've worked here from the second (optimized) Python example in the Wikipedia article for SOS which allows an easy transition to an 'odds only' SOE for comparison.

<~~lang~~ ecmascript>import "/fmt" for Fmt

<syntaxhighlight lang="ecmascript">import "/fmt" for Fmt

import "/seq" for Lst

Line 1,455:

elapsed = ((System.clock - start) * 1000).round

Fmt.print("\nUsing the Sieve of Eratosthenes would have generated them in $,d ms.", elapsed)

Fmt.print("\nAs a check, the $,d Sundaram prime would again have been $,d", 1e6, primes[1e6-1])</~~lang~~>

Fmt.print("\nAs a check, the $,d Sundaram prime would again have been $,d", 1e6, primes[1e6-1])</syntaxhighlight>