素数判定:エラトステネスの篩の実装 C++/D/C#/VB/JS/Python/HSP/LISP

何となくエラトステネスの篩を
C++/D/C#/VB/JS/Python/HSP/LISP
で実装してみました。
実装したついでに[10001番目の素数](http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%20)も適当な個数(110000)の素数リスト作って求めてます。

## C++
```cpp:
#include <iostream>
#include <Math.h>
#include <vector>
using namespace std;

vector<int> sosu(int n){
	vector<int> erst;
	for(int i=0;i<n;i++) erst.push_back(i);
	erst[0]=NULL;
	erst[1]=NULL;
	auto dmax=sqrt(n);

	for(int dx=2;dx<dmax;dx++){
		if(erst[dx]==NULL) continue;
		for(int i=dx*2;i<n;i+=dx){
			erst[i]=NULL;
		}
	}
	
	vector<int> erstlist;
	for(auto i:erst){
		if(i) erstlist.push_back(i);
	}
	return erstlist;
}

int main(){
	for(auto i:sosu(120)){
		cout<<i<<",";
	}
	cout<<endl;
	cout<<sosu(110000)[10000]<<endl;
}
```

## D言語
```d:
import std.stdio;
import std.math;
import std.array;
import std.algorithm;

int[] sosu(int n){
	auto erst=new int[n];
	foreach(i;0..n) erst[i]=i;
	erst[0]=0;
	erst[1]=0;
	auto dmax=sqrt(cast(float)n);

	for(int dx=2;dx<dmax;dx++){
		if(erst[dx]==0) continue;
		for(int i=dx*2;i<n;i+=dx){
			erst[i]=0;
		}
	}
	return array(filter!"a"(erst));
}

void main(){
	writeln(sosu(120));
	writeln(sosu(110000)[10000]);
}
```

## C<span>#</span>
```csharp:
using System;
using static System.Console;
using System.Collections.Generic;
using System.Linq;

class Program{
	static List<int> sosu(int n){
		var erst=new List<int>(Enumerable.Range(0,n));
		erst[0]=0;
		erst[1]=0;
		var dmax=Math.Sqrt(n);

		for(int dx=2;dx<dmax;dx++){
			if(erst[dx]==0) continue;
			for(int i=dx*2;i<n;i+=dx){
				erst[i]=0;
			}
		}
		return erst.Where(i=>i!=0).ToList();
	}

	static void Main(){
		WriteLine(String.Join(",",sosu(120)));
		WriteLine(sosu(110000)[10000]);
	}
}
```

## VB.Net
```vbnet:
Option Strict On
Imports System.Console
Imports System.Collections.Generic
Imports System.Linq

Module Program
	Function sosu(n As Integer) As List(Of Integer)
		Dim erst As New List(Of Integer)(Enumerable.Range(0,n))
		erst(0)=Nothing
		erst(1)=Nothing
		Dim dmax=CInt(Math.Ceiling(Math.Sqrt(n)))

		For dx As Integer=2 To dmax
			If erst(dx)=CInt(Nothing) Then Continue For
			For i=dx*2 To n-1 Step dx
				erst(i)=Nothing
			Next
		Next
		Return erst.Where(Function(i)CBool(i)).ToList()
	End Function

	Sub Main()
		WriteLine(String.Join(",",sosu(120)))
		WriteLine(sosu(110000)(10000))
	End Sub
End Module
```

## JavaScript
```js:
"use strict";
function sosu(n){
	var erst=[...Array(n).keys()];
	[erst[0],erst[1]]=[null,null];
	var dmax=Math.sqrt(n);

	for(let dx=2;dx<dmax;dx=0|dx+1){
		if(!erst[dx]) continue;
		for(let i=dx*2;i<n;i=0|i+dx){
			erst[i]=null;
		}
	}

	return erst.filter(i=>i);
}

console.log(sosu(120));
console.log(sosu(110000)[10000]);
```

## Python3
```py3:
def sosu(n):
	erst=list(range(n))
	erst[0]=erst[1]=None
	import math
	dmax=math.ceil(math.sqrt(n))

	for dx in range(2,dmax):
		if erst[dx] is None: continue
		for i in range(dx*2,n,dx):
			erst[i]=None
	return list(filter(lambda i:i,erst))

print(sosu(120))
print(sosu(110000)[10000])
```

## HSP
```cpp
#runtime "hsp3cl"
#cmpopt varinit 1

#module Program
	#deffunc local sosu int n,array erstlist
		dim erst,n
		foreach erst: erst(cnt)=cnt: loop
		erst(0)=0
		erst(1)=0
		dmax=sqrt(n)
	
		repeat dmax-1,2
			dx=cnt
			if erst(dx)=0: continue
			for i,dx*2,n,dx
				erst(i)=0
			next
		loop

		erstr=""
		foreach erst
			if erst(cnt) {
				if erstr!="": erstr+=","
				erstr+=erst(cnt)
			}
		loop

		sdim erstlistr
		split erstr,",",erstlistr
		dim erstlist,length(erstlistr)
		foreach erstlist
			erstlist(cnt)=int(erstlistr(cnt))
		loop
	return
	#define global sosu(%1,%2) dim %2:sosu@Program %1,%2
#global

sosu 120,a
foreach a: mes a(cnt): loop
sosu 110000,a
mes a(10000)
```

## CommonLisp
```cl:
(defun sosu(n)
	(let (
		(erst (coerce (loop for i from 0 below n collect i) 'vector))
		(dmax (sqrt n)))
			(setf (aref erst 0) nil)
			(setf (aref erst 1) nil)
			(loop for dx from 2 below dmax do
				(when (aref erst dx)
					(loop for i from (* dx 2) below n by dx do
						(setf (aref erst i) nil))))
		(remove nil erst)))

(format t "~A~%" (sosu 120))
(format t "~A~%" (aref (sosu 110000) 10000))
```

## 余談
特に変なことやったつもりはないのだけど、CLだけやたら遅いのは何故なんだろうか…

##### 2017/04/23 追記:
コメントいただいた内容で修正を行いました。