[Codefroce][Python] div.3 #731 - F. Array Stabilization (GCD version)

실패한 코드입니다. 최초는 규칙대로 gcd를 모두 구해가며 진행했으나 TLE가 납니다.

때문에 소인수분해를 해서 각 요소를 제거해가며 풀이하려 했으나 아직 로직이 완벽하지 못합니다. 추후 보완하겠습니다.

 

import sys
input = sys.stdin.readline
from collections import defaultdict

for test in range(int(input())):
    n = int(input())
    a = list(map(int, input().split()))
    cnt = 0
    primes = defaultdict(int)
    for i in range(n):
        tmp = a[i]
        for j in range(2, tmp + 1):
            if tmp == 1:
                break
            if not tmp % j:
                while not tmp % j:
                    tmp //= j
                primes[j] += 1
    print(primes)
    max_cnt = 0
    for prime in primes:
        if not primes[prime] == n and max_cnt < primes[prime]:
            max_cnt = primes[prime]
    print(max_cnt)