The sieve of Sundaram: Difference between revisions

{{trans|Python}}

 

‘

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

sieve_of_Sundaram(100, 1B)

 

 

{{out}}

{{Trans|Nim}}

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.

INT n = 8 000 000;

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

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

FI

{{out}}

<pre>

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

 

if (indexRange's class is list) then

set n1 to beginning of indexRange

end task

 

 

{{output}}

3 5 7 11 13 17 19 23 29 31

37 41 43 47 53 59 61 67 71 73

479 487 491 499 503 509 521 523 541 547

1,000,000th:

 

=={{header|C}}==

#include <stdio.h>

#include <stdlib.h>

}

}

{{out}}

<pre>

<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><br/>

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

using System.Collections.Generic;

using System.Linq;

yield return (v << 1) + 1;

}

{{out}}

Under <strike>1/5</strike> <b><font color=darkgreen>1/8</font></b> of a second @ Tio.run

 

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

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

let sPrimes()=

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

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

{{out}}

<pre>

 

=={{header|Fortran}}==

PROGRAM SUNDARAM

IMPLICIT NONE

END PROGRAM SUNDARAM

 

{{out}}

<pre>

{{trans|Wren}}

{{libheader|Go-rcu}}

 

import (

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)

 

{{out}}

 

=={{header|Haskell}}==

import Data.List.Split (chunksOf)

import qualified Data.Set as S

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

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

{{Out}}

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

 

=={{header|JavaScript}}==

"use strict";

 

 

return main();

{{Out}}

<pre>First 100 Sundaram primes

 

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

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

# limit specified by `.`.

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

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

'''For pretty-printing'''

 

def nwise($n):

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

'''The Tasks'''

Sundaram_primes(100)

| nwise(10)

 

"First hundred:", hundred,

{{out}}

<pre>

=={{header|Julia}}==

{{trans|Python}}

"""

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

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

@time count(primesmask(15485867))

<pre>

3 5 7 11 13 17 19 23 29 31

 

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

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

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

]

SieveOfSundaram[600][[;; 100]]

{{out}}

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

 

=={{header|Nim}}==

 

const N = 8_000_000

if last == 0:

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

 

{{out}}

 

=={{header|Perl}}==

use warnings;

use feature 'say';

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

++$index;

{{out}}

<pre>First 100 Sundaram primes:

 

=={{header|Phix}}==

<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>

<span style="color: #008080;">function</span> <span style="color: #000000;">sos</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">n</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 first 100 odd prime numbers:\n%s\n"</span><span style="color: #0000FF;">,{</span><span style="color: #7060A8;">join_by</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">apply</span><span style="color: #0000FF;">(</span><span style="color: #004600;">true</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">sprintf</span><span style="color: #0000FF;">,{{</span><span style="color: #008000;">"%3d"</span><span style="color: #0000FF;">},</span><span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">..</span><span style="color: #000000;">100</span><span style="color: #0000FF;">]}),</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">10</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 millionth odd prime number: %,d\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1_000_000</span><span style="color: #0000FF;">]})</span>

{{out}}

<pre>

=={{header|Python}}==

===Python :: Procedural===

 

def sieve_of_Sundaram(nth, print_all=True):

 

sieve_of_Sundaram(1000000, False)

<pre>

3 5 7 11 13 17 19 23 29 31

===Python :: Functional===

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

 

from math import floor, log, sqrt

# MAIN ---

if __name__ == '__main__':

{{Out}}

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

{{trans|xxx}}

 

 

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

 

(module+ main

 

{{out}}

 

=={{header|Raku}}==

 

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

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

++$index;

{{out}}

<pre>First 100 Sundaram primes:

=={{header|REXX}}==

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

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

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

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

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

{{out|output|text=&nbsp; when using the default inputs:}}

<pre>

=={{header|Ruby}}==

Based on the Python code from the Wikipedia lemma.

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

k = (n - 3) / 2 + 1

n = 1_000_000

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

{{out}}

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

{{libheader|Wren-seq}}

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.

import "/seq" for Lst

 

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

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

 

{{out}}