Existem diversos métodos para verificar se um número é primo, é claro. Nesta questão, a força bruta não soluciona o problema, pois possui um custo computacional muito alto.

Para quem estava utilizando o método de força bruta (verificar para todo i menor que N, i > 2 se N é divisível por i), basta verificar isso apenas para todo i <= piso da raiz quadrada de n. Todo número composto tem pelo menos um fator primo menor ou igual a raiz dele mesmo. Então, se um número não for divisível para nenhum número menor ou igual a sua raiz, certamente é primo.

A complexidade cai de O(n) para O(sqrt(n)) e já é suficiente para solucionar o problema e remover o erro de Time Limit Exceeded. Mas há métodos ainda mais eficientes que este.