Problem p03194 (python)

Fixed submission:

import collections

# def get_lim(n):
#     # for i in range(n):
#     #     if i * i > n:
#     #         return i + 1
#     return pow(10, int((len(str(n)) / 2)))

def prime_factor(n, length):
    ass = collections.defaultdict(int)
    # break_num = pow()
    # for i in range(2,int(n**0.5)+1):
    # lim = get_lim(n)
    for i in range(2, n):
        # print(pow(i, length),  n)
        # if pow(i, length) > n:
        #     break
        if i * i > n:
            break
        # print(n, i)
        # i = pow(i, num)
        while n % i==0:
            ass[i] += 1
            n = n//i

    if n != 1:
        ass[n] += 1
    return ass

if __name__ == '__main__':
    length, num = list(map(int, input().split()))

    if length == 1:
        print(num)
    else:

        soinnsuu = prime_factor(num, length)
        ans = 1
        # print(soinnsuu)
        for data in soinnsuu.keys():
            if soinnsuu[data] >= length:
               ans *= pow(data, int(soinnsuu[data] / length))
        print(ans)

Buggy submission (verdict: Runtime Error):

import collections

def get_lim(n):
    for i in range(n):
        if i * i > n:
            return i + 1

def prime_factor(n, length):
    ass = collections.defaultdict(int)
    # break_num = pow()
    # for i in range(2,int(n**0.5)+1):
    lim = get_lim(n)
    for i in range(2, lim):
        # print(pow(i, length),  n)
        # if pow(i, length) > n:
        #     break
        if i > n or n == 1:
            break
        # i = pow(i, num)
        while n % i==0:
            ass[i] += 1
            n = n//i

    if n != 1:
        ass[n] += 1
    return ass

if __name__ == '__main__':
    length, num = list(map(int, input().split()))

    if length == 1:
        print(num)
    else:

        soinnsuu = prime_factor(num, length)
        ans = 1
        # print(soinnsuu)
        for data in soinnsuu.keys():
            if soinnsuu[data] >= length:
               ans *= data
        print(ans)

Buggy submission (verdict: Runtime Error):
def prime_factor(n):
    ass = collections.defaultdict(int)
    for i in range(2,int(n**0.5)+1):
        while n % i==0:
            # ass.append(i)
            ass[i] += 1
            n = n//i
    if n != 1:
        ass[n] += 1
    return ass

if __name__ == '__main__':

    # make_seed(num)
    # prime = Prime()
    # soinnsuu = prime.find_factors(num)
    soinnsuu = prime_factor(num)
    ans = 1
    # print(soinnsuu)
    for data in soinnsuu.keys():
        if soinnsuu[data] >= length:
           ans *= data
        # if soinnsuu[data] >= length:
        # ans *= data
    print(ans)

Buggy submission (verdict: Runtime Error):
import math
import random
import collections

length, num = list(map(int, input().split()))

# def make_seed():
#     global length
#     seed_primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]
#     for i in range(len(seed_primes)):
#         seed_primes[i] = pow(seed_primes[i], length)
#     return seed_primes
#
#
# class Prime:
#     seed_primes = make_seed()
#     # print(seed_primes)
#
#     def is_prime(self, n):
#         """
#         prime test (hybrid)
#
#         see also: https://qiita.com/gushwell/items/ff9ed83ba55350aaa369
#
#         :param n:
#         :return: boolean
#         """
#         is_prime_common = self.is_prime_common(n)
#         if is_prime_common is not None:
#             return is_prime_common
#
#         if n < 2000000:
#             return self.is_prime_brute_force(n)
#         else:
#             return self.is_prime_miller_rabin(n)
#
#     def is_prime_common(self, n):
#         if n == 1: return False
#         if n in Prime.seed_primes: return True
#         if any(map(lambda x: n % x == 0, self.seed_primes)): return False
#
#     def is_prime_brute_force(self, n):
#         """
#         brute force prime test
#         use with is_prime_common if you want to skip seed_primes
#
#         :param n:
#         :return: boolean
#         """
#         for k in range(2, int(math.sqrt(n)) + 1):
#             if n % k == 0:
#                 return False
#         return True
#
#     def is_prime_miller_rabin(self, n):
#         """
#         miller rabin prime test
#         use with is_prime_common if you want to skip seed_primes
#
#         see also
#             algorithm: https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test
#             implementation: https://qiita.com/srtk86/items/609737d50c9ef5f5dc59
#             improvement: https://qiita.com/gushwell/items/ff9ed83ba55350aaa369
#
#         :param n:
#         :return: boolean
#         """
#
#         d = n - 1
#         while d & 1 == 0:
#             d >>= 1
#
#         # use one of these lines / upper is more efficient.
#         witnesses = self.get_witnesses(n)
#         # witnesses = [random.randint(1, n - 1) for _ in range(100)]
#
#         for w in witnesses:
#             y = pow(w, d, n)
#
#             while d != n - 1 and y != 1 and y != n - 1:
#                 y = (y * y) % n
#                 d <<= 1
#
#             if y != n - 1 and d & 1 == 0:
#                 return False
#
#         return True
#
#     def get_witnesses(self, num):
#         def _get_range(num):
#             if num < 2047:
#                 return 1
#             if num < 1373653:
#                 return 2
#             if num < 25326001:
#                 return 3
#             if num < 3215031751:
#                 return 4
#             if num < 2152302898747:
#                 return 5
#             # if num < 3474749660383:
#             #     return 6
#             # if num < 341550071728321:
#             #     return 7
#             # if num < 3825123056546413051:
#             #     return 9
#             return 12
#         # print(self.seed_primes[:_get_range(num)])
#
#         return self.seed_primes[:_get_range(num)]
#
#     def gcd(self, a, b):
#         if a < b:
#             return self.gcd(b, a)
#         if b == 0:
#             return a
#         while b:
#             a, b = b, a % b
#         return a
#
#     @staticmethod
#     def f(x, n, seed):
#         """
#         pseudo prime generator
#         :param x:
#         :param n:
#         :param seed:
#         :return: pseudo prime
#         """
#         p = Prime.seed_primes[seed % len(Prime.seed_primes)]
#         return (p * x + seed) % n
#
#     def find_factor(self, n, seed=1):
#         global length
#         """
#         find one of factor of n
#         this function is based to Pollard's rho algorithm
#
#         see also
#             algorithm: https://en.wikipedia.org/wiki/Pollard%27s_rho_algorithm
#             implementation: https://qiita.com/gushwell/items/561afde2e00bf3380c98
#
#         :param n:
#         :param seed:
#         :return: factor
#         """
#         if self.is_prime(n):
#             return n
#
#         x, y, d = 2, 2, 1
#         count = 0
#         while d == 1:
#             count += 1
#             x = self.f(x, n, seed)
#             y = self.f(self.f(y, n, seed), n, seed)
#             d = self.gcd(abs(x - y), n)
#
#         d = pow(d, length)
#
#         if d == n:
#             return self.find_factor(n, seed+1)
#         return self.find_factor(d)
#
#     def find_factors(self, n):
#         primes = {}
#         if self.is_prime(n):
#             primes[n] = 1
#             return primes
#
#         while n > 1:
#             factor = self.find_factor(n)
#             print(factor)
#
#             primes.setdefault(factor, 0)
#             primes[factor] += 1
#
#             n //= factor
#
#         print(primes)
#
#         return primes

# def make_seed(num):
#     global seed_primes
#     for i in range(len(seed_primes)):
#         seed_primes[i] = pow(seed_primes[i], num)

#nの素因数分解(O(n**0.5)
def prime_factor(n):
    ass = collections.defaultdict(int)
    for i in range(2,int(n**0.5)+1):
        while n % i==0:
            # ass.append(i)
            ass[i] += 1
            n = n//i
    if n != 1:
        ass.append(n)
    return ass

if __name__ == '__main__':

    # make_seed(num)
    # prime = Prime()
    # soinnsuu = prime.find_factors(num)
    soinnsuu = prime_factor(num)
    ans = 1
    # print(soinnsuu)
    for data in soinnsuu.keys():
        if soinnsuu[data] >= length:
           ans *= data
        # if soinnsuu[data] >= length:
        # ans *= data
    print(ans)

Buggy submission (verdict: Runtime Error):
import sympy
a = sympy.factorint(2016)
print(a)