The sieve of Eratosthenes: you've been there; done that; have the T-shirt. The sieve of Eratosthenes was ancient history when Euclid was a schoolboy. You are ready for something less than 3000 years old. You are ready for The sieve of Sundaram.

Starting with the ordered set of +ve integers, mark every third starting at 4 (4;7;10...).

Step through the set and if the value is not marked output 2*n+1. So from 1 to 4 output 3 5 7.

4 is marked so skip for 5 and 6 output 11 and 13.

7 is marked, so no output but now also mark every fifth starting at 12 (12;17;22...)

as per to 10 and now mark every seventh starting at 17 (17;24;31....)

as per for every further third element (13;16;19...) mark every (9th;11th;13th;...) element.

The output will be the ordered set of odd primes.

Using your function find and output the first 100 and the millionth Sundaram prime.

The faithless amongst you may compare the results with those generated by The sieve of Eratosthenes.

References

 The article on Wikipedia.


import strutils
 
const N = 8_000_000
 
type Mark {.pure.} = enum None, Mark1, Mark2
 
var mark: array[1..N, Mark]
for n in countup(4, N, 3): mark[n] = Mark1
 
 
var count = 0           # Count of primes.
var list100: seq[int]   # First 100 primes.
var last = 0            # Millionth prime.
var step = 5            # Current step for marking.
 
for n in 1..N:
  case mark[n]
  of None:
    # Add/count a new odd prime.
    inc count
    if count <= 100:
      list100.add 2 * n + 1
    elif count == 1_000_000:
      last = 2 * n + 1
      break
  of Mark1:
    # Mark new numbers using current step.
    if n > 4:
      for k in countup(n + step, N, step):
        if mark[k] == None: mark[k] = Mark2
      inc step, 2
  of Mark2:
    # Ignore this number.
    discard
 
 
echo "First 100 Sundaram primes:"
for i, n in list100:
  stdout.write ($n).align(3), if (i + 1) mod 10 == 0: '\n' else: ' '
echo()
if last == 0:
  quit "Not enough values in sieve. Found only $#.".format(count), QuitFailure
echo "The millionth Sundaram prime is ", ($last).insertSep()