А какие простые ты проверял?

Ну до sqrt(A[i])

А если остается число

То +1 простое число само число оставшеесся

Ну как минимум надо поставить отсечение, что суммарная степень простого должна быть хотя бы N (иначе оно точно войдет в ответ со степенью 0).

Это по идее гарантирует, что общий объем работы не превысит суммарную длину разложение на простые, а она небольшая.

Еще, возможно, надо поускорять факторизацию, 10^5 * sqrt(10^6) это довольно много

Давайте чутка проясним, правильно ли я вообще делаю и думаю
Я создал изначально массив с праймами до sqrt(1e6) так как ну это максимальное значение элемента массива.
Потом я создал двумерный массив для каждого элемента и в Matr[i][N] я буду хранить сколько простых чисел в числе A[i] Nого разряда N здесь порядковое число простых чисел.
После этого я иду с макс N и пытаюсь сделать так чтобы общая сумма в массиве Matr[i] равнялась размеру массива

Это правильная мысль вообще?

Кстати, да

Из за этого я и получил tl

Двумерные массивы меня смущают. Они на самом деле будут очень разреженными, то есть ты делаешь много лишней рабоиы

Я предлагаю по-другому писать.

1. Факторизовать все числа.

2. В массиве cnt для каждого простого посчитать его суммарную степень.

3. Далее, если cnt[p] >= n, то обработать его за O(n)

А в каком виде хранить факторизацию чисел

просто в массиве cnt?

Типа if (A[j]%prime[i] ==0) cnt[i]++;

Ну например, ты можешь сначала заранее вычислить все простые до 10^3, а потом идти только по ним при факторизации, так ты ускоришь ее  в несколько раз.

Нет, он опять же будет очень разреженным (простых до 1е6 довольно много, порядка 1е5, а не-нулей будет штук 15 от силы). Лучше в хэш-таблице.

Хорошо

если числа до 1e6, можно заранее факторизацию всех чисел прекалькнуть

в два фора

там кажется самое простое
maxprime[i] = наибольший простой делитель i
и дальше

for (int i = 2; i <= LIMIT; ++i)
  if (maxprime[i] == 0)
    for (int j = i + i; j <= LIMIT; j += i)
      maxprime[j] = i;

сорт решета