#include using namespace std; typedef long long ll; #define MAX 1000005 ll sieve_size; bitset<1000010> bs; // 10^7 + espacio extra vector primes; // Lista de números primos void sieve(ll n) // n: Tamaño de la criba { sieve_size=n; bs.set(); bs[0] = bs[1] = 0; for(ll i = 2; i <= n; i++) if(bs[i]) { for(ll j = i * i; j <= n; j += i) { bs[j] = 0; } primes.push_back(i); } } int isPrime(ll n) // n: Número a verificar { if(n <= sieve_size && bs.test(n)) return 1; // O(1) para números en la criba for(int i = 0; i < (int)primes.size(); i++) // Para cada número primo.. { ll p = primes[i]; if(n % p == 0) return p; // Si el primo lo divide, no es primo if(p * p > n) return 1; // Si excedimos la raiz de n, es primo } return 1; } int main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); sieve(MAX); int n; cin >> n; ll ans=0; vector a(n); for (int i = 0; i < n; i++) { cin >> a[i]; ans+=(a[i]==1?0:1); int aux=isPrime(a[i]); //cout<