Python/Ruby/PHP/Golang(Go)で素数を扱う

#Python/Ruby/PHP/Go(Golang)で素数を扱う
競技プログラミングに参加するとほぼどのサイトでも確実に登場する素数問題。
指定された整数以下について素数を求める、ある整数か素数かどうか判別する、ときには素因数分解が必要なケースがあるので、それぞれの対応が必要だった。
なお、Rubyには`Prime`クラスがあるが、ここでは利用しない。

##指定された整数以下について素数を求める
「エラトステネスの篩」で実現する。

###エラトステネスの篩
素数を求めるアルゴリズム自体は古代ギリシャから存在するとのこと。[Wikipedia](https://ja.wikipedia.org/wiki/%E3%82%A8%E3%83%A9%E3%83%88%E3%82%B9%E3%83%86%E3%83%8D%E3%82%B9%E3%81%AE%E7%AF%A9)の説明が非常にわかりやすい。そこで包除原理（個数定理）にも同時に出会う。
包除原理を利用した実例は、[ここ](http://qiita.com/hiroykam/items/3886d6a213cd593fdfab)に記載。

###エラトスネスの篩の実装
1000以下の正の整数について、素数を出力する。便宜上、いずれの方法でも、1001までの要素を持つ配列を作成し、素数かどうか判定できるようにした。

####Python3でエトステネスの篩

```py
def prime(maximum):
    sieve = [True] * maximum

    def sieved(prime):
        for not_prime in range(prime + prime, len(sieve), prime):
            sieve[not_prime] = False

    sieve[0] = sieve[1] = False
    sieved(2)
    for x in range(3, int(maximum ** 0.5) + 1, 2):
        if sieve[x]: sieved(x)
    return [prime for prime, is_prime in enumerate(sieve) if is_prime]

if __name__ == '__main__':
    print(prime(1001))
```

※[shiracamus](http://qiita.com/shiracamus)さんからご指摘いただいた内容です。

####Ruby2.4でエラトステネスの篩
Python3のコードをベースに作成。

```rb
def prime(maximum)
  sieve = Array.new(maximum, true)

  sieved = lambda do |prime|
    ((prime + prime)..sieve.length).step(prime).each do |not_prime|
      sieve[not_prime] = false
    end
  end

  sieve[0], sieve[1] = false, false
  sieved.call(2)
  (3..(maximum ** 2).to_i).step(2).each do |x|
    sieved.call(x) if sieve[x]
  end

  sieve
end

prime(10001).each_with_index do |f, x|
  p x if f
end
```

####PHP7.1でエラトステネスの篩
Python3のコードをベースに作成。

```php
<?php

function prime(int $maximum) : array {
    $sieve = [];
    $sieve[0] = $sieve[1] = false;
    array_walk(range(2, $maximum - 1), function ($i) use(&$sieve) { $sieve[$i] = true; });

    $sieved = function (int $prime) use(&$sieve) : void {
        array_walk(range($prime + $prime, count($sieve) - 1, $prime),  function($not_prime) use(&$sieve) : void {
            $sieve[$not_prime] = false;
        });
    };
    $sieved(2);
    array_walk(range(3, intval($maximum ** 0.5), 2), function ($x) use(&$sieve, $sieved) : void {
        if ($sieve[$x]) $sieved($x);
    });
    return array_filter($sieve);
}

array_walk(array_keys(prime(1001)), function ($prime) { print($prime. PHP_EOL); });
```

####GoLangでエラトステネスの篩
Python3のコードをベースに作成。

```go
package main

import (
	"fmt"
    "math"
)

func prime(maximum int) [] bool {
	sieve := make([]bool, maximum)
	for i := range sieve {
		sieve[i] = true
	}

	sieved := func(prime int) {
		for i := prime + prime; i < maximum; i += prime {
			sieve[i] = false
		}
	}

	sieve[0] = false; sieve[1] = false
	sieved(2)
	end := int(math.Pow(float64(maximum), 0.5) + 1)
	for i := 3; i < end; i += 2 {
		if sieve[i] {
			sieved(i)
		}
	}

	return sieve
}

func main() {
	maximum := 1001
	print_prime := func () {
		for value, is_prime := range prime(maximum) {
			if is_prime {
				fmt.Printf("%v\n", value)
			}
		}
	}
	print_prime()
}
```

##ある整数が素数かどうか調べる
エラトステネスの篩を利用した上述のコードを利用することもできるが、余計な計算もあるため、この場合パフォーマンスがでない。そこで、アルゴリズムについて考える。

1) `2`,`3`,`5`を素数として扱う
2) `2`以外の偶数は素数ではない
3) `3`,`5`で割り切れたら素数ではない
4) `7`以上の整数についてインクリメントしてき、ある整数に対して剰余算で`0`からどうかチェックしていく。ただし、インクリメントは奇数のときは`4`、偶数のときは`2`インクリメントする。

###Python3である整数が素数かどうか調べる
```py
def is_prime(n):
    if n < 2:
        return False
    if n == 2 or n == 3 or n == 5:
        return True
    if not n & 1:
        return False
    if n % 2 == 0 or n % 3 == 0 or n % 5 == 0:
        return False

    f, v, m = True, 7, int(n ** 0.5) + 1
    while v < m:
        if n % v == 0: return False
        v += 4 if f else 2
        f = not f
    return True


if __name__ == '__main__':
    print(is_prime(4993)) # True
```

###Ruby2.4である整数が素数かどうか調べる
```rb
def prime?(n)
  if n < 2
    false
  elsif n == 2 || n == 3 || n == 5 then true
  elsif n & 1 == 0 then false
  elsif n % 2 == 0 || n % 3 == 0 || n % 5 == 0 then false
  else
    f, v, m = true, 7, (n ** 0.5).to_i + 1
    while v < m do
      if n % v == 0
        false
        return
      end
      v += f ? 4 : 2
      f = !f
    end
    true
  end
end

p prime?(4993) # -> true
```

###PHPである整数が素数かどうか調べる
```php7.1
<?php

function is_prime(int $n) : bool {
    $r = true;
    if ($n < 2) $r = false;
    elseif ($n == 2 || $n == 3 || $n == 5) $r = true;
    elseif ($n & 1 == 0) $r = false;
    elseif ($n % 2 == 0 || $n % 3 == 0 || $n % 5 == 0) $r = false;
    else {
        $f = true;
        $v = 7;
        $m = intval($n ** 0.5) + 1;
        while ($v < $m) {
            if ($n % $v == 0) {
                $r = false;
                break;
            }
            $v += $f ? 4 : 2;
            $f = !$f;
        }
    }
    return $r;
}

print(is_prime(4993) ? "true" : "false");
```

###Golangである整数が素数かどうか調べる
```go
package main

import (
    "fmt"
    "math"
)

func is_prime(n int) bool {
    switch {
    case n < 2:
       return false
    case n == 2 || n == 3 || n == 5:
       return true
    case n & 1 == 0:
       return false
    case n % 2 == 0 || n % 3 == 0 || n % 5 == 0:
       return false
    }
    
    f := true
    v := 7
    m := int(math.Pow(float64(n), 0.5)) + 1
    for v < m {
        if n % v == 0 {
            return false
        }
        if f {
            v += 4
        } else {
            v += 2
        }
        f = !f
    }
    return true
}

func main() {
    fmt.Print(is_prime(4993))  // true
}
```

##ある整数を素因数分解
利用経験はほとんどないが、素数に関連しているので、それぞれ実現してみる。

###Python3である整数を素因数分解
Pythonには[SymPy](http://www.sympy.org/en/index.html)があるが、[stackoverflow](https://stackoverflow.com/questions/15347174/python-finding-prime-factors)で回答されていた方法で実現した。

```py
def prime_factors(n):
    i, factors = 2, []
    while i * i <= n:
        if n % i:
            i += 1
        else:
            n /= i
            factors.append(i)
    if n > 1:
        factors.append(n)
    return factors

if __name__ == '__main__':
    print(prime_factors(1200))  # [2, 2, 2, 2, 3, 5, 5]
```

###Ruby2.4である整数を素因数分解
```rb
def prime_factor(n)
  i, factors = 2, []
  while i * i <= n do
    if n % i != 0
      i += 1
    else
      n /= i
      factors.push(i)
    end
  end
  if n > 1
    factors.push(n)
  end
  factors
end

p prime_factor(1200) # -> [2, 2, 2, 2, 3, 5, 5]
```
###PHP7.1である整数を素因数分解

```php
<?php

function prime_factors(int $n) : array {
    $i = 2;
    $factors = [];
    while ($i * $i <= $n) {
        if ($n % $i) $i += 1;
        else {
            $n /= $i;
            $factors[] = $i;
        }
    }
    if ($n > 1) $factors[] = $n;
    return $factors;
}

print_r(prime_factors(1200)); // [2, 2, 2, 2, 3, 5, 5]
```

###Golangである整数を素因数分解

```go
package main

import "fmt"

func prime_factors(n int) [] int {
    factors := make([]int, 0)
    i := 2
    for i * i <= n {
        r := n % i
        if r != 0 {
            i += 1
        } else if r == 0 {
            n /= i
            factors = append(factors, i)
        }
    }
    if n > 1 {
        factors = append(factors, n)
    }
    return factors
}

func main() {
    fmt.Print(prime_factors(1200))  // [2 2 2 2 3 5 5]
}
```