Considerando a eficiência de memória e a complexidade de tempo, selecione a função que é a mais eficiente, mantendo-se uma implementação válida.

Vamos comparar tempo e memória (assumindo $n>1$ e que todas são implementações válidas).

Função A

• Testa divisores de $2$ até $\lfloor\sqrt{n}\rfloor$.
• Tempo: no pior caso (quando $n$ é primo), faz cerca de $\sqrt{n}$ testes ⇒ $O(\sqrt{n})$.
• Memória: usa apenas variáveis de controle ⇒ $O(1)$.

Função B

• Cria um array com todos os números de $2$ a $n-1$.
• Depois percorre e vai removendo elementos do array (remoção em array geralmente custa $O(n)$ por remoção, pois exige deslocamentos).
• Tempo: no pior caso pode chegar a comportamento quadrático devido às remoções ⇒ tipicamente $O(n^2)$ (ou, no mínimo, pior que $O(n)$).
• Memória: armazena um array de tamanho ~$n$ ⇒ $O(n)$.

Função C

• Testa todos os $i$ de $1$ até $n$ (exceto 1 e o próprio $n$ como divisores “úteis”).
• Tempo: no pior caso (primo), faz ~$n$ testes ⇒ $O(n)$.
• Memória: apenas variáveis de controle ⇒ $O(1)$.

Conclusão

Comparando:

• A: $O(\sqrt{n})$ tempo e $O(1)$ memória
• B: pior em memória ($O(n)$) e tempo (tende a $O(n^2)$)
• C: $O(n)$ tempo e $O(1)$ memória

Logo, a mais eficiente em tempo e memória é a Função A.

Alternativa correta: (A).