#Python/Ruby/PHP/Go(Golang)で素数を扱う
競技プログラミングに参加するとほぼどのサイトでも確実に登場する素数問題。
指定された整数以下について素数を求める、ある整数か素数かどうか判別する、ときには素因数分解が必要なケースがあるので、それぞれの対応が必要だった。
なお、RubyにはPrimeクラスがあるが、ここでは利用しない。
##指定された整数以下について素数を求める
「エラトステネスの篩」で実現する。
###エラトステネスの篩
素数を求めるアルゴリズム自体は古代ギリシャから存在するとのこと。Wikipediaの説明が非常にわかりやすい。そこで包除原理（個数定理）にも同時に出会う。
包除原理を利用した実例は、ここに記載。
###エラトスネスの篩の実装
1000以下の正の整数について、素数を出力する。便宜上、いずれの方法でも、1001までの要素を持つ配列を作成し、素数かどうか判定できるようにした。
####Python3でエトステネスの篩
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さんからご指摘いただいた内容です。
####Ruby2.4でエラトステネスの篩
Python3のコードをベースに作成。
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
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のコードをベースに作成。
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()
}
##ある整数が素数かどうか調べる
エラトステネスの篩を利用した上述のコードを利用することもできるが、余計な計算もあるため、この場合パフォーマンスがでない。そこで、アルゴリズムについて考える。
-
2,3,5を素数として扱う -
2以外の偶数は素数ではない -
3,5で割り切れたら素数ではない -
7以上の整数についてインクリメントしてき、ある整数に対して剰余算で0からどうかチェックしていく。ただし、インクリメントは奇数のときは4、偶数のときは2インクリメントする。
###Python3である整数が素数かどうか調べる
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である整数が素数かどうか調べる
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である整数が素数かどうか調べる
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があるが、stackoverflowで回答されていた方法で実現した。
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である整数を素因数分解
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
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である整数を素因数分解
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]
}