Problem p02574 (python)

Fixed submission:
import sys
from math import gcd
def input(): return sys.stdin.readline().strip()

def main():
    N = int(input())
    A =list(map(int, input().split()))

    all_gcd = A[0]
    max_num = A[0]
    for a in A:
        all_gcd = gcd(all_gcd, a)
        max_num = max(max_num, a)
    if all_gcd != 1:
        print("not coprime")
        return

    # エラトステネスの篩でprimes[i] = (iを割り切る最小の素数)を記録する
    min_prime = [i for i in range(max_num + 1)]
    for p in range(2, int(max_num**0.5) + 1):
        if min_prime[p] != p: continue
        for i in range(2, max_num // p + 1): min_prime[i * p] = p

    used = [0] * (max_num + 1)
    for a in A:
        while a > 1:
            p = min_prime[a]
            if used[p]:
                print("setwise coprime")
                return
            while a % p == 0: a //= p
            used[p] = 1
    print("pairwise coprime")




if __name__ == "__main__":
    main()

Buggy submission (verdict: Runtime Error):
import sys
from math import gcd
def input(): return sys.stdin.readline().strip()

def fast_prime_factorization(A, max_num):
    """
    リストAに現れる自然数全てをO(NlogN)で素因数分解する（NはリストAの長さ）
    max_numはAに現れる自然数の上界。
    """
    # エラトステネスの篩でprimes[i] = (iを割り切る最小の素数)を記録する
    primes = [0] * (max_num + 1)
    for i in range(2, int(max_num**0.5) + 1):
        if primes[i] != 0: continue
        for j in range(i, max_num + 1, i):
            if primes[j] == 0: primes[j] = i

    # factorization[i] = {p1:n1, p2:n2, ...} (A[i] = p1^{n1} * p2^{n2} * ...)
    factorization_list = [{} for _ in range(len(A))]
    for i, a in enumerate(A):
        while a > 1:
            if primes[a] not in factorization_list[i]:
                factorization_list[i][primes[a]] = 1
            else:
                factorization_list[i][primes[a]] += 1
            a //= primes[a]

    return factorization_list


def main():
    N = int(input())
    A =list(map(int, input().split()))

    all_gcd = A[0]
    for a in A:
        all_gcd = gcd(all_gcd, a)
    if all_gcd != 1:
        print("not coprime")
        return

    prime_factor_list = fast_prime_factorization(A, 10**6)
    d = set()
    for factor_dict in prime_factor_list:
        for prime in factor_dict:
            if prime in d:
                print("setwize coprime")
                return
            d.add(prime)
    print("pairwise coprime")




if __name__ == "__main__":
    main()

Buggy submission (verdict: Runtime Error):
import sys
from math import gcd
def input(): return sys.stdin.readline().strip()

def main():
    N = int(input())
    A =list(map(int, input().split()))
    A.sort()

    idx = 0
    while A[idx] == 1: idx += 1
    A = A[idx:]
    if idx == N:
        print("pairwise coprime")
        return

    all_gcd = A[0]
    for a in A:
        all_gcd = gcd(all_gcd, a)
    if all_gcd != 1:
        print("not coprime")
        return

    prod = A[0]
    for i, a in enumerate(A):
        if i == 0: continue
        if gcd(prod, a) != 1:
            print("setwise coprime")
            return
        prod *= a
    print("pairwise coprime")




if __name__ == "__main__":
    main()

Buggy submission (verdict: Runtime Error):
import sys
from math import gcd
def input(): return sys.stdin.readline().strip()

def main():
    N = int(input())
    A =list(map(int, input().split()))
    A.sort()

    idx = 0
    while A[idx] == 1: idx += 1
    A = A[idx:]

    all_gcd = A[0]
    for a in A:
        all_gcd = gcd(all_gcd, a)
    if all_gcd != 1:
        print("not coprime")
        return

    prod = A[0]
    for i, a in enumerate(A):
        if i == 0: continue
        if gcd(prod, a) != 1:
            print("setwise coprime")
            return
        prod *= a
    print("pairwise coprime")




if __name__ == "__main__":
    main()