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

Introduction

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

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 *.

Ruby Python Perl Java
Code length 247 Byte 567 Byte 571 Byte 1419 Byte
Execution time 24 ms 87 ms 11 ms 104 ms
memory 3964 KB 3316 KB 512 KB 23892 KB

Summary

Referenced site

Recommended Posts

Solving with Ruby, Perl, Java and Python AtCoder CADDi 2018 C Prime Factorization
Solving with Ruby and Python AtCoder ARC067 C Prime Factorization
Solving with Ruby, Perl, Java, and Python AtCoder ABC 065 C factorial
Solving with Ruby and Python AtCoder ABC057 C Prime Factorization Bit Search
Solving with Ruby, Perl, Java, and Python AtCoder ARC 098 C Cumulative sum
Solving with Ruby, Perl, Java and Python AtCoder ATC 002 A
Solving with Ruby, Perl, Java and Python AtCoder ATC 002 B
Solving with Ruby, Perl, Java and Python AtCoder diverta 2019 Programming Contest C String Manipulation
Solving with Ruby, Perl, Java and Python AtCoder ABC 107 B String Manipulation
Benchmark for C, Java and Python with prime factorization
Solving with Ruby, Perl, Java, and Python AtCoder AGC 033 A Breadth-first search
Solving with Ruby, Perl, Java and Python AtCoder ABC 165 D Floor function
Solving with Ruby, Perl, Java and Python AtCoder ABC 131 D Array Sorting
Solve with Ruby, Perl, Java and Python AtCoder ABC 047 C Regular Expression
Solving with Ruby and Python AtCoder ARC 059 C Least Squares
Solving with Ruby and Python AtCoder ABC011 C Dynamic programming
Solving with Ruby and Python AtCoder Tenka1 Programmer Contest C Cumulative sum
Sorting AtCoder ARC 086 C hashes to solve in Ruby, Perl, Java and Python
Solving with Ruby and Python AtCoder CODE FESTIVAL 2016 qual C B Priority queue
Solving with Ruby and Python AtCoder ABC178 D Dynamic programming
Solving with Ruby and Python AtCoder ABC151 D Breadth-first search
Solving with Ruby and Python AtCoder AISING2020 D Iterative Squares
Solving with Ruby and Python AtCoder ABC153 E Dynamic programming
Solving with Ruby and Python AtCoder ABC138 D Adjacency list
Solving in Ruby, Python and Java AtCoder ABC141 D Priority Queuing
Solve with Ruby, Python and Java AtCoder ARC104 B Cumulative sum
Solving with Ruby, Python and numpy AtCoder ABC054 B Matrix operation
Solving with Ruby, Python and networkx AtCoder ABC168 D Adjacency list
Solving with Ruby AtCoder ABC110 C String Manipulation
Solve with Ruby and Python AtCoder ABC084 D Cumulative sum of prime numbers
Solve with Ruby and Python AtCoder ABC133 D Cumulative sum
Scraping with Node, Ruby and Python
Solved AtCoder ABC 114 C-755 with Python3
List split and join strings with split and join (Perl / PowerShell / Java / Kotlin / Python)
Encrypt with Ruby (Rails) and decrypt with Python
Easy web scraping with Python and Ruby
RaspberryPi L Chika with Python and C #
AtCoder ABC172 C Cumulative Sum Binary Search Solved by Ruby and Python
AtCoder Beginner Contest 170 B Problem "Crane and Turtle" Explanation (Python3, C ++, Java)
MessagePack-Try to link Java and Python with RPC
Solving the Lorenz 96 model with Julia and Python
Challenge AtCoder (ABC) 164 with Python! A ~ C problem
paiza POH ec-campaign (C # / Java / Python / Ruby) # paizahack_01
2014 Web Application Framework Trends (PHP / Java / Ruby / Python / Perl)
AtCoder ARC080 D simulation solved in Ruby and Python
AtCoder Beginner Contest 176 C Problem "Step" Explanation (Python3, C ++, Java)
Investigate Java and python data exchange with Apache Arrow
Comparison of CoffeeScript with JavaScript, Python and Ruby grammar
Version control of Node, Ruby and Python with anyenv
Solve AtCoder 167 with python
Ruby, Python and map
Python and Ruby split
AtCoder JSC2019 Qual B to solve with Ruby and Python Inverse element of arithmetic progression
AtCoder Beginner Contest 166 A Explanation of Problem "A? C" (Python3, C ++, Java)
AtCoder Beginner Contest 174 B Problem "Distance" Explanation (C ++, Python, Java)
AtCoder Beginner Contest 177 B Problem "Substring" Explanation (Python3, C ++, Java)
[AtCoder explanation] Control ABC180 A, B, C problems with Python!
[AtCoder explanation] Control ABC188 A, B, C problems with Python!
Mandelbrot Benchmark (C, PHP, HHVM, Ruby, Python, PyPy, and Kinx)
Five languages basic grammar comparison (C #, Java, Python, Ruby, Kotlin)
AtCoder Beginner Contest 167 A Problem "Registration" Explanation (Python3, C ++, Java)