Problem p02574 (python)

Fixed submission:
from collections import defaultdict

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

Ones = A.count(1)
R = max(A)
nums = [0]*(R+1)

# 素因数テーブルの作成
D = [0]*(R+1)
for i in range(2, R+1):
    if D[i]:
        continue
    n = i
    while n < R+1:
        if D[n] == 0:
            D[n] = i
        n += i

# 素因子をカウント
for a in A:
    tmp = a
    while tmp > 1:
        prime_factor = D[tmp]
        nums[prime_factor] += 1
        while tmp%prime_factor == 0:
            tmp //= prime_factor
y = max(nums)
if y < 2:
    print('pairwise coprime')
elif y-Ones < N:
    print('setwise coprime')
else:
    print('not coprime')

Buggy submission (verdict: Runtime Error):
N = int(input())
A = [0]*(100001)
IIL = list(map(int, input().split()))
for a in IIL:
    A[a] += 1

# MFPF = Most Frequent Prime Factor
MFPF_n = 0
for i in range(2, 100001):
    n = i
    tmp = 0
    while n < 100001:
        tmp += A[n]
        n += i
    MFPF_n = max(MFPF_n, tmp)

if MFPF_n < 2:
    print('pairwise coprime')
elif MFPF_n - A[1] < N:
    print('setwise coprime')
else:
    print('not coprime')

Buggy submission (verdict: Runtime Error):
N = int(input())
A = [0]*(100001)
for a in list(map(int, input().split())):
    A[a] += 1

# MFPF = Most Frequent Prime Factor
MFPF_n = 0
for i in range(2, 100001):
    n = i
    tmp = 0
    while n < 100001:
        tmp += A[n]
        n += i
    MFPF_n = max(MFPF_n, tmp)

if MFPF_n < 2:
    print('pairwise coprime')
elif MFPF_n - A[1] < N:
    print('setwise coprime')
else:
    print('not coprime')

Buggy submission (verdict: Runtime Error):
# 入力
N = int(input())
A = list(map(int, input().split()))

# 入力前処理
# 1はいくつあっても関係ないので除く
A = [x for x in A if x > 1]
N = len(A)

R = max(A)
prime_factor_counter = [0]*(R+1)

# D[x]にxを割り切れる最初の素数を格納
# 次に行う素因数分解で試し割りのムダを削減するための前準備
D = [0]*(R+1)
for i in range(2, R+1):
    if D[i]:
        continue
    n = i
    while n < R+1:
        if D[n] == 0:
            D[n] = i
        n += i

# 素因数分解し、素因子をカウント
# ex: 12 => 2と3のカウントを+1する
for a in A:
    tmp = a
    while tmp > 1:
        prime_factor = D[tmp]
        prime_factor_counter[prime_factor] += 1
        while tmp%prime_factor == 0:
            tmp //= prime_factor

# 回答出力
if max(prime_factor_counter) < 2:
    print('pairwise coprime')
elif max(prime_factor_counter) < N:
    print('setwise coprime')
else:
    print('not coprime')

Buggy submission (verdict: Runtime Error):
from collections import defaultdict

def prime_factors(n):
    arr = []
    temp = n
    R = int(-(-n**0.5//1))
    furui = [0]*(R+1)
    for i in range(2, R+1):
        if furui[i]:
            continue
        if temp%i == 0:
            while temp%i == 0:
                temp //= i
            arr.append(i)
        m = i
        while m < R+1:
            furui[m] = 1
            m += i

    if temp != 1:
        arr.append(temp)

    return arr

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

nums = defaultdict(int)

for a in A:
    for x in prime_factors(a):
        nums[x] += 1

y = max(nums.values())

if y < 2:
    print('pairwise coprime')
elif y < N:
    print('setwise coprime')
else:
    print('not coprime')

Buggy submission (verdict: Runtime Error):
from collections import defaultdict

def prime_factors(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i == 0:
            while temp%i == 0:
                temp //= i
            arr.append(i)

    if temp != 1:
        arr.append(temp)

    return arr

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

nums = defaultdict(int)

for a in A:
    for x in prime_factors(a):
        nums[x] += 1

y = max(nums.values())

if y < 2:
    print('pairwise coprime')
elif y < N:
    print('setwise coprime')
else:
    print('not coprime')

Buggy submission (verdict: Runtime Error):
N = int(input())
A = list(map(int, input().split()))
A.sort()
R = int(A[-1]**0.5)

is_pairwise_coprime = True
is_setwise_coprime = True
checked = [0]*(R+2)
l = 0

for i in range(2, R+2):
    if checked[i]:
        continue
    
    # 調べる範囲を狭める
    while A[l] < i:
        l += 1
    if l == N-1:
        break
    
    # iで割り切れるAiの個数を数える
    tmp = 0
    for j in range(l, N):
        if A[j]%i == 0:
            tmp += 1
    # 2個以上あればnot pairwise coprime
    # N個あれば not setwise coprime
    if tmp > 1:
        is_pairwise_coprime = False
    if tmp == N:
        is_setwise_coprime = False
    
    if is_setwise_coprime == False:
        break
    
    # iの倍数はチェック済みにする
    n = i
    while n < R+2:
        checked[n] = 1
        n += i
    # print(checked, l)
if is_pairwise_coprime:
    print('pairwise coprime')
elif is_setwise_coprime:
    print('setwise coprime')
else:
    print('not coprime')

Buggy submission (verdict: Runtime Error):
N = int(input())
A = list(map(int, input().split()))
A.sort()
m = A[0]
R = int(A[-1]**0.5)

is_pairwise_coprime = True
is_setwise_coprime = True
checked = [0]*(R+2)
l = 0
for i in range(2, R+2):
    if checked[i]:
        continue
    
    while A[l] < i:
        l += 1
    
    if l == N-1:
        break
    
    tmp = 0
    for j in range(l, N):
        if A[j]%i == 0:
            tmp += 1

    if tmp > 1:
        is_pairwise_coprime = False
    if tmp == N:
        is_setwise_coprime = False
    
    if is_setwise_coprime == False:
        break
    
    n = i
    while n < R+2:
        checked[n] = 1
        n += i
    # print(checked, l)
if is_pairwise_coprime:
    print('pairwise coprime')
elif is_setwise_coprime:
    print('setwise coprime')
else:
    print('not coprime')