Solving with Ruby, Perl, Java and Python AtCoder CADDi 2018 C Prime Factorization

Introduction

• AtCoder Problems * Use Recommendations to solve past problems. Thanks to AtCoder and AtCoder Problems.

This theme

AtCoder CADDi C - Product and GCD Difficulty: 772

This theme, prime factorization + hash Ruby When the 972439611840 of input example 4 is factorized into prime factors, it becomes{2 => 6, 3 => 3, 5 => 1, 103 => 4}. Divide this into N integers to get the answer. Less than N prime numbers do not contribute to the greatest common divisor.

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 * has a standard prime library that handles prime numbers, and prime_division does prime factorization. ~~ It's too cheat. ~~ You can also generate prime numbers with generator.next, so the prime problem seems to have an advantage in *** 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):

I defined a function for the first time in * Python *, but it seems that an error will occur if I do not define it before using it. 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;
}

For the prime factorization function, refer to @ sugyan's * How to make a prime factorization one-liner, part 1 *. 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;
    }
}

For the prime factorization function, refer to * Introduction to Easy Java Programming *.

Summary

• Solved CADDi 2018 C
• Become familiar with Ruby
• Become familiar with Python
• Become familiar with Perl
• Become familiar with Java

Referenced site

• prime library *
• How to make a prime factorization one-liner, part 1 *
• Introduction to Easy Java Programming *