エラトステネスの篩で素数を取り出す。（C#、Java、JavaScript、PHP、Python3、Ruby）

　２から整数nまでの素数を調べる方法は、それぞれの数値を素因数分解して約数が２つ（１とその数自身）である数を見つけていく方法に加えて、「エラトステネスの篩」という方法があります。

　エラトステネスの篩を使うと、素因数分解で素数を調べていく方法よりも少ない計算量で整数nまでの素数を見つけることが可能です。

素因数分解で素数を調べていく方法の計算量 …… O(n√n)
エラトステネスの篩で素数を調べていく方法の計算量 …… O(nloglogn)

　エラトステネスの篩は、２から整数nの平方根までの整数について、nを越えないような２以上の整数倍の数値を消していき、残った数値が素数になります。

２×２、２×３・・・２×m ＜＝ n
３×２、３×３・・・３×m ＜＝ n
・
・
・
√n×２、√n×２・・・√n×m ＜＝ n

　今回はエラトステネスの篩で素数を求めるコードを、Ｃ#、Java、JavaScript、PHP、Python3、Rubyの６言語で書いてみました。

　エラトステネスの篩で素数を調べる手順は、大きく分けて３つの処理になってます。

１．配列の0からnまでの要素として、素数であることを示す値（ここでは1）を入れていきます。正の整数の素数は２以上ですが、言語によっては空の要素があるとエラーが出るので、添字0から要素を入れていきます。
２．エラトステネスの篩を用いて、２以上の添字について、素数でない添字の要素に0を入れていきます。
３．２以上の添字について、要素が1であればその添字を素数として出力します。

using System;
using System.Linq;
using System.Collections.Generic;

public class Test{
    public static void Main(){
        //標準入力から数値を読み込む
        var n = int.Parse(Console.ReadLine().Trim());

        //素数フラグ1を設定
        var num = new List<int>();

        for (int i = 0; i <= n; i++){
            num.Add(1);
        }

        //素数以外のフラグを0にする
        for (int j = 2; j <= Math.Sqrt(n); j++){
            int m = 2;
            while (j * m <= n){
                num[j * m] = 0;
                m += 1;
            }
        }

        //素数のみを出力
        for (int k = 2; k <= n; k++){
            if (num[k] == 1){
                 Console.WriteLine(k);
            }
        }
    }
}

Java

public class Main {
    public static void main(String[] args) throws Exception {
        //標準入力から数値を読み込む
        Scanner scan = new Scanner(System.in);
        var n = Integer.parseInt(scan.nextLine().trim());

        //素数フラグ1を設定
        List<Integer> num = new ArrayList<>();
        for (int i = 0; i <= n; i++){
            num.add(1);
        }

        //素数以外のフラグを0にする
        for(int j = 2; j <= Math.sqrt(n); j++){
            int m = 2;

            while (j * m <= n){
                num.set(j * m, 0);
                m += 1;
            }
        }

        //素数のみを出力
        for (int k = 2; k <= n; k++){

            if (num.get(k) == 1){
                System.out.println(k);
            }
        }
    }
}

JavaScript

process.stdin.resume();
process.stdin.setEncoding('utf8');

var lines = [];
var reader = require('readline').createInterface({
  input: process.stdin,
  output: process.stdout
});
reader.on('line', (line) => {
  lines.push(line);
});
reader.on('close', () => {
    //標準入力から数値を読み込む
    var n = parseInt(lines[0]);

    //素数フラグ1を設定
    var num = [];

    for (var i = 0; i <= n; i++){
        num[i] = 1;
    }

    //素数以外のフラグを0にする
    for (var j = 2; j <= Math.sqrt(n); j++){
        var m = 2;
        while (j * m <= n){
            num[j * m] = 0;
            m += 1;
        }
    }

    //素数のみを出力
    for (var k = 2; k <= n; k++){
        if (num[k] == 1){
            console.log(k);
       }
    }
});

PHP

<?php
//標準入力から数値を読み込む
$n = trim(fgets(STDIN));

//素数フラグ1を設定
$num = [];

for ($i = 0; $i <= $n; $i++){
    $num[$i] = 1;
}

//素数以外のフラグを0にする
for ($j = 2; $j <= sqrt($n); $j++){
    $m = 2;

    while ($j * $m <= $n){
        $num[$j * $m] = 0;
        $m += 1;
    }
}

//素数のみを出力
for ($k = 2; $k <= $n; $k++){
    if ($num[$k] == 1){
        echo $k."\n";
    }
}
?>

Python3

import math

#標準入力から数値を読み込む
n = int(input().rstrip())

#素数フラグ1を設定
num = []
for i in range(0,n+1):
    num.append(1)

#素数以外のフラグを0にする
for j in range(2, int(math.sqrt(n) + 1)):
    m = 2

    while j * m <= n:
        num[j * m] = 0
        m += 1

#素数のみを出力
for k in range(2, n+1):
    if num[k] == 1:
        print(k)

Ruby

#標準入力から数値を読み込む
n = gets.chomp.to_i

#素数フラグ1を設定
num = []

for i in 0..n
    num[i] = 1
end

#素数以外のフラグを0にする
for j in 2..Math.sqrt(n)
    m = 2
    while j * m <= n
       num[j * m] = 0
       m += 1
    end
end

#素数のみを出力
for k in 2..n
    if num[k] == 1
        puts k
    end
end