Questão nº 61
Questão de Tecnologia da Informação · FGV SMF-RJ 2023 - Manhã (P1) (nº 61)
Considere a existência de uma tabela relacional N, com apenas uma coluna, intitulada numero, contendo os números inteiros de 1 até 100, um em cada linha, como ilustrada a seguir.
Como pode haver discrepâncias entre implementações da linguagem SQL, é dado que a função sqrt(x) retorna a raiz quadrada de x e que a expressão a % b retorna o resto da divisão inteira de a por b.
Numa definição simplificada, números primos são os números inteiros a partir de 2 que só são divisíveis por eles mesmos e o número 1.
Assinale o comando SQL que produz a lista de todos, e somente, os números primos presentes na tabela N, descrita anteriormente.
- A
- B
- C
- D
(alternativa correta) - E
Resposta comentada
Gabarito Alternativa D
Um número primo é um número inteiro maior que 1 que só pode ser dividido exatamente por 1 e por ele mesmo. Para verificar se um número é primo, procuramos por divisores (números que o dividem sem deixar resto) entre 2 e a raiz quadrada desse número. Se nenhum divisor for encontrado nesse intervalo, o número é primo.
- (A) Incorreta: Esta consulta exclui todos os números maiores que 1. A condição
N1.numero % N2.numero = 0noEXISTSserá sempre verdadeira paraN2.numero = N1.numero(já que todo número é divisível por si mesmo), fazendo com queNOT EXISTSseja sempre falsa. Assim, nenhum número seria retornado. - (B) Incorreta: Embora esta consulta produza o resultado correto, ela é menos eficiente do que a alternativa D. A condição
N2.numero < N1.numerofaz com que o SQL verifique divisores atéN1.numero - 1. Matematicamente, basta verificar divisores até a raiz quadrada do número, tornando esta busca mais longa do que o necessário e, portanto, uma solução subótima. - (C) Incorreta: Similar à alternativa A, esta consulta exclui todos os números maiores que 1. A condição
N2.numero <= N1.numeropermite queN2.numeroseja igual aN1.numero, o que faz com queN1.numero % N2.numero = 0seja sempre verdadeiro. Isso resulta emEXISTSser sempre verdadeiro eNOT EXISTSser sempre falso, não retornando nenhum número. - (D) Correta: Esta é a forma mais eficiente e matematicamente otimizada para identificar números primos. A consulta seleciona
N1.numerose ele for maior que 1 e se não existir nenhumN2.numero(potencial divisor) tal queN2.numeroseja maior que 1,N2.numeroseja menor ou igual à raiz quadrada deN1.numero(sqrt(N1.numero)) eN1.numeroseja divisível porN2.numero(N1.numero % N2.numero = 0). A verificação até a raiz quadrada é suficiente porque se um númerontem um divisord > sqrt(n), ele também deve ter um divisorn/d < sqrt(n). - (E) Incorreta: Assim como a alternativa B, esta consulta produz o resultado correto, mas é menos eficiente que a alternativa D. A condição
N2.numero <= N1.numero / 2faz com que o SQL verifique divisores até a metade deN1.numero. Embora seja uma otimização em relação a verificar atéN1.numero - 1, ainda é menos eficiente do que verificar apenas atésqrt(N1.numero), que é o limite matemático mais restrito para a busca de divisores.
Fonte: FGV SMF-RJ 2023 - Manhã (P1) Fiscal de Rendas (Caderno Tipo 1). Reproduzida para fins de estudo.