from sys import stdin,stdout
from math import *
def read_list_line(elem_func=int):
return [elem_func(x) for x in stdin.readline().strip().split()]
def read_line(elem_func=str):
return elem_func(stdin.readline().strip())
def print_list_line(the_list,elem_func=str,sep=' ',end=""):
st=(sep.join([elem_func(x) for x in the_list]))+end
stdout.write(st)
return st
def print_line(st):
stdout.write(str(st)+"\n")
return st
maxa=31625
is_prime=[True]*(maxa)
primes=[]
is_prime[0]=False
is_prime[1]=False
for i in range(2,maxa):
if (is_prime[i]==True):
j=i
while ((i*j)<maxa):
is_prime[(i*j)]=False
j += 1
primes.append(i)
ntest=read_line(int)
def main():
global is_prime, primes, maxa
n = read_line(int)
a = read_list_line(int)
a.sort()
p_set=set()
for i in range(n):
x = a[i]
for p in primes:
if a[i] % p == 0:
if p in p_set:
print("YES")
return 0
p_set.add(p)
while (x % p == 0):
x = x // p
if x > 1:
if x in p_set:
print("YES")
return 0
p_set.add(x)
print("NO")
return 0
for test_case in range(1,1+ntest):
main()/*
* Author: UnPolinomio
* Time: 2023-01-30 02:18:51
**/
#include <bits/stdc++.h>
using namespace std;
#define _ \
ios_base::sync_with_stdio(false); \
cin.tie(0); \
cout.tie(0)
#define deb(x) cout << #x << ": " << (x) << '\n';
#define all(x) begin(x), end(x)
#define fore(x, a, b) for(lli x = a, ___lim___=b; x < ___lim___; ++x)
using lli = long long int;
using vi = vector<lli>;
using vb = vector<bool>;
using ii = pair<lli, lli>;
vi primes(lli n) {
vb p(n + 1, true);
for(lli i{2}; i * i <= n; ++i) {
if(!p[i]) continue;
for(lli j{i * i}; j <= n; j += i) p[j] = false;
}
vi ans{};
fore(i, 2, n + 1) if(p[i]) ans.push_back(i);
return ans;
}
bool solve(vi& a) {
static vi ps{ primes(ceil(sqrt(1000000000)))};
unordered_set<lli> s{};
for(auto &el : a) {
for(auto p : ps) {
if(el % p == 0) {
if(s.count(p)) return true;
while(el % p == 0) el /= p;
s.insert(p);
}
}
}
for(auto &el : a) {
if(el == 1) continue;
if(s.count(el)) return true;
s.insert(el);
}
return false;
}
int main() {
_;
lli t{}, n{};
cin >> t;
while(t--) {
cin >> n;
vi a(n);
for(auto &el : a) cin >> el;
cout << (solve(a) ? "YES" : "NO") << '\n';
}
return EXIT_SUCCESS;
}
485A - Factory | 628A - Tennis Tournament |
1436B - Prime Square | 1707B - Difference Array |
1422C - Bargain | 1611F - ATM and Students |
660A - Co-prime Array | 1692F - 3SUM |
1470A - Strange Birthday Party | 190D - Non-Secret Cypher |
1721B - Deadly Laser | 1721C - Min-Max Array Transformation |
1721A - Image | 1180C - Valeriy and Deque |
557A - Ilya and Diplomas | 1037D - Valid BFS |
1144F - Graph Without Long Directed Paths | 1228A - Distinct Digits |
355B - Vasya and Public Transport | 1230A - Dawid and Bags of Candies |
1530A - Binary Decimal | 1472D - Even-Odd Game |
441C - Valera and Tubes | 1328E - Tree Queries |
265A - Colorful Stones (Simplified Edition) | 296A - Yaroslav and Permutations |
967B - Watering System | 152A - Marks |
1398A - Bad Triangle | 137A - Postcards and photos |