The Sieve of Sundaram (1934)

sundaram.cr

def sieve_sundaram(n : UInt64)
	a = Hash(UInt64, Bool).new
	s = Array(UInt64).new
	m = (n/2.0).round
	(1_u64..n).each do |i|
		(i..n).each do |j|
			p = i + j + 2_u64*i*j
			if p <= n
				a[p] = true
			end
		end
	end
	(1_u64..m).each do |k|
		if !a.has_key?(k)
			q = 2_u64*k + 1
			s.push(q)
		end
	end

	return s
end

sieve_sundaram(1000)

sundaram.d

import std.stdio;

void main () {
	sieve_sundaram(10000);
}

auto sieve_sundaram (ulong n) {
	bool[ulong] a;
	ulong[] s = [2];
	ulong m = n/2;
	foreach (i; 1..n) {
		foreach (j; i..n) {
			ulong p = i + j + 2*i*j;
			if (p <= n) {
				a[p] = true;
			}
		}
	}
	foreach (k; 1..m) {
		bool* r = (k in a);
		if (r is null) {
			ulong q = 2*k + 1;
			s ~= q;
		}
	}

	return s;
}

sundaram.dart

void main() {
	sieve_sundaram(1000);
}

sieve_sundaram(int n) {
	var a = {};
	var s = [2];
	var m = (n/2).round();
		for (var i = 1; i < n; i++) {
		for (var j = i; j < n; j++) {
			var p = i + j + 2*i*j;
		if (p <= n) a[p] = true;
		}
	}
	for (var k = 1; k < m; k++) {
		if (a[k] == null) {
			var q = 2*k + 1;
			s.add(q);
		}
	}

	return s;
}

sundaram.go

package main

import "fmt"

func main() {
	sieve_sundaram(1000)
}

func sieve_sundaram(n int) []int {
	a := make(map[int]bool)
	s := []int{2}
	m := n/2
	for i := 1; i < n; i++ {
		for j := i; j < n; j++ {
			p := i + j + 2*i*j
			if p <= n {
				a[p] = true
			}
		}
	}
	for k := 1; k < m; k++ {
		if !a[k] {
			q := 2*k + 1
			s = append(s, q)
		}
	}

	return s
}

sundaram.janet

(defn sundaram [n]
  ((def a (table))
   (for i 1 n
     (for j i n
       (def p (+ i j (* 2 i j)))
       (if (<= p n) (put a p true))))
   )
  (def s @[2])
  (for k 1 (/ n 2)
    (if (not (get a k)) (array/push s (+ 1 (* 2 k))))
  ) s)
(pp (sundaram 10000))

sundaram.jl

#!/usr/bin/env julia

function sieve_sundaram(n)
	a = Set()
	s = [2]
	m = n/2
	for i = 1:n, j = i:n
		p = i + j + 2*i*j
		if p <= n
			push!(a, p)
		end
	end
	for k = 1:m
		if ! in(k, a)
			q = 2*k + 1
			push!(s, q)
		end
	end

	return s
end

sieve_sundaram(1000)

sundaram.js

#!/usr/bin/env node

'use strict'

function sieve_sundaram(n) {
	let a = {}
	let s = [2]
	let m = Math.round(n/2);
	for (let i = 1; i < n; i++) {
		for (let j = i; j < n; j++) {
			let p = i + j + 2*i*j
			if (p <= n) a[p] = true
		}
	}
	for (let k = 1; k <= m; k++) {
		if (!a[k]) {
			let q = 2*k + 1
			s.push(q)
		}
	}

	return s
}

sieve_sundaram(1000)

sundaram.lua

#!/usr/bin/env lua

-- The Sieve of Sundaram (1934): a deterministic algorithm
-- for finding all the prime numbers up to a specific value

function sieve_sundaram(n)
	local a = {}
	local s = {2}
	local m = n/2
	for i = 1, n do
		for j = i, n do
			local p = i + j + 2*i*j
			if p <= n then
				a[p] = true
			end
		end
	end
	for k = 1, m do
		if not a[k] then
			local q = 2*k + 1
			table.insert(s, q)
		end
	end

	return s
end

sieve_sundaram(1000)

sundaram.pl

#!/usr/bin/env perl

use strict;
use warnings;

sub sieve_sundaram {
	my $n = shift;

	my %a;
	my @s = (2);
	my $m = $n/2;
	foreach my $i (1..$n) {
		foreach my $j ($i..$n) {
			my $p = $i + $j + 2*$i*$j;
			if ($p <= $m) {
				$a{$p} = 1;
			}
		}
	}
	foreach my $k (1..$m) {
		if (! $a{$k}) {
			my $q = 2*$k + 1;
			push(@s, $q);
		}
	}

	return \@s;
}

sieve_sundaram(1000);

sundaram.py

#!/usr/bin/env python

def sieve_sundaram(n):
	a = set()
	s = [2]
	m = int(round(n/2.0))
	for i in range(1, n):
		for j in range(i, n):
			p = i + j + 2*i*j
			if (p <= m):
				a.add(p)
	for k in range(1, m):
		if (k not in a):
			q = 2*k + 1
			s.append(q)
	return s

sieve_sundaram(1000)

sundaram.raku

#!/usr/bin/env raku

sub sieve_sundaram(int $n) {
	my %a;
	my int @s = <2>;
	my int $m = ($n/2).round;
	for 1..$n -> int $i {
		for $i..$n -> int $j {
			my int $p = $i + $j + 2*$i*$j;
			if $p <= $m {
				%a{$p} = True;
			}
		}
	}
	for 1..$m -> int $k {
		if ! %a{$k} {
			my int $q = 2*$k + 1;
			@s.push($q);
		}
	}

	return @s;
}

sieve_sundaram(1000);

sundaram.rb

#!/usr/bin/env ruby

def sieve_sundaram(n)
	a = Hash.new
	s = Array.new
	m = (n/2.0).round
	for i in 1..n do
		for j in i..n do
			p = i + j + 2*i*j
			if p <= n
				a[p] = true;
			end
		end
	end
	for k in 1..m do
		if not a[k]
			q = 2*k + 1
			s.push(q)
		end
	end

	return s
end

sieve_sundaram(1000)

sundaram.rkt

#lang racket
(require racket/set)
(define (sundaram n)
  (define a
    (for*/set ([i (in-range 1 n)]
             [j (in-range i n)]
             #:when (<= (+ i j (* 2 i j)) n))
    (+ i j (* 2 i j))))
  (define s
    (for/list ([k (in-range 1 (/ n 2))]
            #:when (not (set-member? a k)))
    (+ 1 (* 2 k))))
  (append '(2) s))
(sundaram 10000)

sundaram.rs

use std::collections::HashSet;

fn main() {
	sieve_sundaram(1000);
}

fn sieve_sundaram(n: u64) -> Vec<u64> {
	let mut a: HashSet<u64> = HashSet::new();
	let mut s: Vec<u64> = vec![2];
	let m = n/2;
	for i in 1..n {
		for j in i..n {
			let p = i + j + 2*i*j;
			if p <= n {
				a.insert(p);
			}
		}
	}
	for k in 1..m {
		if !a.contains(&k) {
			let q = 2*k + 1;
			s.push(q);
		}
	}
	return s;
}

sundaram.tcl

proc sieve_sundaram {n} {
	global a {}
	set s { 2 }
	set m [expr {$n / 2}]
	for {set i 1} {$i < $n} {incr i} {
		for {set j $i} {$j < $n} {incr j} {
			set p [expr {$i + $j + 2 * $i * $j}]
			if {$p <= $n} {
				set a($p) 1
			}
		}
	}
	for {set k 1} {$k <= $m} {incr k} {
		if {![info exists a($k)]} {
			set q [expr {2 * $k + 1}]
			lappend s $q
		}
	}
	return $s
}

sieve_sundaram 1000