bằng c++ xuất ra dưới 1 giây

#include <bits/stdc++.h>
using namespace std;
bool isPrime(long long n) {
    if (n <= 1) return false;
    for (long long i = 2; i <= sqrt(n); i++)
        if (n % i == 0) return false;
    return true;
}
bool baUoc(long long n) {
    long long sr = sqrt(n);
    if (sr*sr != n) return false;
    return isPrime(sr);
}
int main() {
    //freopen("UOC.INP","r",stdin);
    //freopen("UOC.OUT","w",stdout);
    int n,a,count = 0;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a;
        if (baUoc(a)) count++;
    }
    cout << count;
    return 0;
}

Một số chỉ có đúng 3 ước khi nó có dạng `p^2` với `p` là một số nguyên tố.

Vậy ta chỉ cần lặp qua dãy, kiểm tra xem `\sqrt(a_i)` có phải số nguyên tố không.

$\\$
Code tham khảo:

#include <iostream>
#include <cmath>

#define ll long long

using namespace std;

bool is_prime(ll x) {
  if (x < 2) return false;
  for (ll i=2; i*i<=x; ++i) {
    if (x % i == 0) return false;
  }
  return true;
}

bool accept(ll x) {
  ll s = sqrt(x);
  if (s * s != x) return false;
  return is_prime((ll)s);
}

int main() {
  int n, x, res=0; cin >> n;
  while (n --> 0) {
    cin >> x;
    res += accept(x);
  }
  cout << res;
}

$\\$
$\\$
\begin{array}{c|c|c}\color{#ffd710}{\texttt{\{}} \color{#8655d6}{\texttt{\{}}\ \ \color{#8cdcda}{\text{Daoanhviet96}}\ \ \color{#8655d6}{\texttt{\}}} \color{#ffd710}{\texttt{\}}}\end{array}