#include <bits/stdc++.h>
using namespace std;
const int maxN = 1000000;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
vector<int> minPrime(maxN + 1, 0);
vector<int> primes;
for (int i = 2; i <= maxN; i++) {
if (minPrime[i] == 0) {
minPrime[i] = i;
primes.push_back(i); }
for (int j = 0; j < primes.size(); j++) {
int p = primes[j];
if (1LL * i * p > maxN) break;
minPrime[i * p] = p;
if (i % p == 0) break; } }
int n;
cin>>n;
vector<int> a(n);
for (int i = 0; i < n; i++) cin>>a[i];
vector<bool> hasPrime(maxN + 1, false);
for (int i = 0; i < n; i++) {
int x = a[i];
while (x > 1) {
int p = minPrime[x];
hasPrime[p] = true;
while (x % p == 0) x /= p; } }
}
