SRM599 div2 Med

BigFatInteger2.py

import collections
import math

class BigFatInteger2:
  def isDivisible(self, A, B, C, D):
    As = self._prime_decomposition(A)
    Cs = self._prime_decomposition(C)

    print As, Cs
    for c in set(Cs):
      if c not in As:
        return "not divisible"

    Acount = collections.Counter(As)
    Ccount = collections.Counter(Cs)

    for a_key, a_value in Acount.items():
      if a_value * B < Ccount[a_key] * D:
        return "not divisible"

    return "divisible"


  def _prime_decomposition(self, n):
    array = []
    primes = self.primetable(int(math.ceil(math.sqrt(n))))
    for p in primes:
      while n % p == 0:
        n /= p
        array.append(p)
      if n == 1:
        break
    else:
      array.append(n)

    return array

  def primetable(self, max):
    sq = math.sqrt(max)
    table = []

    t = range(0, max+1)
    t[0] = 0
    t[1] = 0
    p = 2
    while p <= sq:
      if t[p] != 0:
        j = p + p
        while j <= max:
          t[j] = 0
          j += p
      p += 1
    for p in t:
      if p != 0:
        table.append(p)
    return table