#include typedef struct tree { struct tree *p; } tree; tree *get_root (tree *t) { if (t == NULL || t->p == NULL) { return t; } t->p = get_root(t->p); return t->p; } int main () { int n = 0; int a = 0; int res = 0; int ans = 0; int cnt = 0; tree t[200000] = {}; tree *tp[200001] = {}; res = scanf("%d", &n); for (int i = 0; i < n; i++) { int tmp = 0; t[i].p = NULL; res = scanf("%d", &a); tmp = a; for (int p = 2; p*p <= a; p++) { if (tmp%p == 0) { if (tp[p] != NULL) { tree *rt = get_root(tp[p]); if (rt != t+i) { rt->p = t+i; cnt++; } } tp[p] = t+i; while (tmp%p == 0) { tmp /= p; } } } if (tmp > 1) { if (tp[tmp] != NULL) { tree *rt = get_root(tp[tmp]); if (rt != t+i) { rt->p = t+i; cnt++; } } tp[tmp] = t+i; } } if (tp[2] != NULL) { ans = (n-cnt-1)*2; } else if (tp[3] != NULL && cnt == n-2) { ans = 3; } else if (cnt < n-1) { ans = (n-cnt)*2; } printf("%d\n", ans); return 0; }