Ruby と Perl と Java と Python で解く AtCoder CADDi 2018 C 素因数分解

# はじめに
*[AtCoder Problems](https://kenkoooo.com/atcoder/#/)* の Recommendation を利用して、過去の問題を解いています。
AtCoder さん、AtCoder Problems さん、ありがとうございます。
# 今回のお題
*[AtCoder CADDi C - Product and GCD](https://atcoder.jp/contests/caddi2018/tasks/caddi2018_a)*
<font color="brown">Difficulty: 772</font>

今回のテーマ、素因数分解 ＋ ハッシュ
# Ruby
入力例 4 の`972439611840`を素因数分解しますと、`{2=>6, 3=>3, 5=>1, 103=>4}`となります。
これを N 個の整数に分配すれば解答が求まります。N 個未満の素数は、最大公約数に寄与しないわけです。

```ruby.rb
require 'prime'

n, p = gets.split.map(&:to_i)
if p == 1
  puts 1
elsif n == 1
  puts p
else
  h = Prime.prime_division(p).to_h
  ans = 1
  h.each do |k, v|
    while v >= n
      ans *= k
      v -= n
    end
  end
  puts ans
end
```
```prime.rb
require 'prime'

h = Prime.prime_division(p).to_h
```

*Ruby* には素数を扱う`prime`ライブラリが標準であり、`prime_division`で素因数分解をやってくれます。~~チート過ぎです。~~
他にも`generator.next`で素数を生成できますので、素数問題は ***Ruby*** にアドバンテージがあると思われます。
# Python
```python.py
from collections import defaultdict
from math import sqrt

n, p = map(int, input().split())
h = defaultdict(int)
def factorization(arg):
    while arg % 2 == 0:
        h[2] += 1
        arg /= 2
    for i in range(3, int(sqrt(arg)) + 1, 2):
        while arg % i == 0:
            h[i] += 1
            arg /= i
    if arg > 1:
        h[arg] += 1
if p == 1:
    print(1)
elif n == 1:
    print(p)
else:
    factorization(p)
    ans = 1
    for k, v in h.items():
        while v >= n:
            ans *= k
            v -= n
    print(ans)
```
```def.py
def factorization(arg):
```
*Python* で初めて関数を定義しましたが、使用する前に定義しないとエラーになる様です。
# Perl
```perl.pl
chomp (my ($n, $p) = split / /, <STDIN>);
my %h;

if ($p==1) {
  print "1\n";
} elsif ($n==1) {
  print "$p\n";
} else {
  factorization($p);
  my $ans = 1;
  for my $k (keys %h) {
    my $v = $h{$k};
    while ($v >= $n) {
      $ans *= $k;
      $v -= $n;
    }
  }
  print "$ans\n";
}
sub factorization {
  my $arg = shift;
  while ($arg % 2 == 0) {
    $h{2}++;
    $arg /= 2;
  }
  for my $i (3..sqrt($arg)) {
    if ($arg % $i == 0) {
      $h{$i}++;
      return ($i, factorization($arg / $i));
    }
  }
  $h{$arg}++ if $arg > 1;
}
```
```fac.pl
sub factorization {
  my $arg = shift;
  while ($arg % 2 == 0) {
    $h{2}++;
    $arg /= 2;
  }
  for my $i (3..sqrt($arg)) {
    if ($arg % $i == 0) {
      $h{$i}++;
      return ($i, factorization($arg / $i));
    }
  }
  $h{$arg}++ if $arg > 1;
}
```
素因数分解の関数は、@sugyan さんの*[素因数分解ワンライナーの作り方 その１](https://memo.sugyan.com/entry/20090130/1233284733)* を参照させていただきました。
# Java
```java.java
import java.util.*;

class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long n = Long.parseLong(sc.next());
        long p = Long.parseLong(sc.next());
        sc.close();
        if (p == 1) {
            System.out.println(1);
        } else if (n == 1) {
            System.out.println(p);
        } else {
            HashMap<Long, Long> h = factorization(p);
            long ans = 1;
            for (long k : h.keySet()) {
                long v = h.get(k);
                while (v >= n) {
                    ans *= k;
                    v -= n;
                }
            }
            System.out.println(ans);
        }
    }

    static HashMap<Long, Long> factorization(long p) {
        HashMap<Long, Long> h = new HashMap<>();
        while (p % 2 == 0) {
            if (h.containsKey(2L)) {
                h.put(2L, h.get(2L) + 1);
            } else {
                h.put(2L, 1L);
            }
            p /= 2;
        }
        for (long i = 3; i * i <= p; i += 2) {
            while (p % i == 0) {
                if (h.containsKey(i)) {
                    h.put(i, h.get(i) + 1);
                } else {
                    h.put(i, 1L);
                }
                p /= i;
            }
        }
        if (p > 1)
            h.put(p, 1L);
        return h;
    }
}
```
素因数分解の関数は、*[お気楽 Java プログラミング入門](http://www.nct9.ne.jp/m_hiroi/java/abcjava02.html)* を参照させていただきました。

||Ruby|Python|Perl|Java|
|:--:|:--:|:--:|:--:|:--:|
|コード長|247 Byte|567 Byte|571 Byte|1419 Byte|
|実行時間|24 ms|87 ms|11 ms|104 ms|
|メモリ|3964 KB|3316 KB|512 KB|23892 KB|
# まとめ
+ CADDi 2018 C を解いた
+ Ruby に詳しくなった
+ Python に詳しくなった
+ Perl に詳しくなった
+ Java に詳しくなった

参照したサイト
*[primeライブラリ](https://docs.ruby-lang.org/ja/latest/library/prime.html)*
*[素因数分解ワンライナーの作り方 その１](https://memo.sugyan.com/entry/20090130/1233284733)*
*[お気楽 Java プログラミング入門](http://www.nct9.ne.jp/m_hiroi/java/abcjava02.html)*