JavaScript
VB.Net
common-lisp
HSP
エラトステネスの篩

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

More than 1 year has passed since last update.

何となくエラトステネスの篩を

C++/D/C#/VB/JS/Python/HSP/LISP

で実装してみました。

実装したついでに10001番目の素数も適当な個数(110000)の素数リスト作って求めてます。


C++

#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言語

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#

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

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

"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

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

#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

(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 追記:

コメントいただいた内容で修正を行いました。