toms.log: いろんな言語で素因数分解

再帰関数の比較.

Elixirで素因数分解を解く問題があったので, これをいろんな言語で書いてみた. 素因数分解を行う関数は関数の引数として与えた正の整数に対して素因数分解した配列を返す.

$ factors(12)
[2, 2, 3]

Elixirの特徴を活かして再帰で実装する.

C++17

C++ではラムダ式を使って再帰を行った. キャプチャとかもあってまあまあ複雑. 実際にこんなコードを書くことはないと思う.

	#include <iostream>
	#include <functional>
	#include <vector>

	std::vector<int> factors(int number) {
	std::function<std::vector<int>(int, int, std::vector<int>)> fact = [&fact](int number, int divider, std::vector<int> l) -> std::vector<int> {
	if (number == 1) {
	return l;
	} else if (number % divider == 0) {
	l.push_back(divider);
	return fact(number/divider, divider, l);
	} else {
	return fact(number, ++divider, l);
	}
	};

	std::vector<int> l = {};
	return fact(number, 2, l);
	}

	void print(std::vector<int> vec) {
	std::cout << "[";
	for (auto i=vec.begin();i!=--vec.end();++i) {
	std::cout << *i << ", ";
	}
	std::cout << *(--vec.end()) << "]" << std::endl;
	}

	int main() {
	auto result1 = factors(12);
	print(result1);
	auto result2 = factors(1024);
	print(result2);
	auto result3 = factors(1031);
	print(result3);

	return 0;
	}

view raw prime_factors.cpp hosted with ❤ by GitHub

C++に比べてかなりシンプル. type hint は対して意味ない. Pythonだと再帰に制限がかかっている.

	import sys

	sys.setrecursionlimit(2000)

	def factors(number: int):
	"""
	>>> factors(12)
	[2, 2, 3]
	>>> factors(2**10)
	[2, 2, 2, 2, 2, 2, 2, 2, 2, 2]
	>>> factors(1031)
	[1031]
	"""
	return _factors(number, 2, [])

	def _factors(number: int, divider: int, l: list[int]):
	if number == 1:
	return l
	elif number % divider == 0:
	l.append(divider)
	return _factors(number // divider, divider, l)
	else:
	return _factors(number, divider+1, l)

	import doctest
	doctest.testmod()

view raw prime_factors.py hosted with ❤ by GitHub

問題は整数の扱いくらい. たぶんTypescriptで書いてもほとんど変わらない.

	const factors = number => {
	return _factors(number, 2, []);
	}

	const _factors = (number, divider, l) => {
	if (number === 1) {
	return l;
	} else if (number % divider === 0) {
	return _factors(Math.floor(number/divider), divider, l.concat(divider));
	} else {
	return _factors(number, divider+1, l);
	}
	}

	const assert = (expected, actual) => {
	console.assert(expected === actual, `expected ${expected}, but was$ {actual}.`);
	}

	assert(JSON.stringify([2,2,3]), JSON.stringify(factors(12)));
	assert(JSON.stringify([2,2,2,2,2,2,2,2,2,2]), JSON.stringify(factors(2**10)));
	assert(JSON.stringify([1031]), JSON.stringify(factors(1031)));

view raw prime_factors.js hosted with ❤ by GitHub

本命のElixir. Elixirが得意そうな処理なので当然だが特徴的なコードになった.

	defmodule PrimeFactors do
	@doc """
	Caluculate the prime factors of a number
	## Parameters
	- `number` - The number to calculate the factors of
	## Examples
	iex> PrimeFactors.factors(12)
	[2, 2, 3]
	iex> PrimeFactors.factors(2**10)
	[2, 2, 2, 2, 2, 2, 2, 2, 2, 2]
	iex> PrimeFactors.factors(1031)
	[1031]
	"""
	def factors(number) do
	factors(number, 2, [])
	end

	defp factors(1, _, l) do
	l
	\|> Enum.reverse()
	end

	defp factors(number, divider, l) when rem(number, divider) == 0 do
	factors(div(number, divider), divider, [divider \| l])
	end

	defp factors(number, divider, l) do
	factors(number, divider + 1, l)
	end
	end

view raw prime_factors.ex hosted with ❤ by GitHub

	defmodule PrimeFactorsTest do
	use ExUnit.Case
	doctest PrimeFactors
	end

言語仕様に沿ってコードが書けるかということは言語仕様の設計意図を適切に読み解くことが必要.