Flashcard FC329838
Como verificar se um número inteiro n é primo usando o teste até a raiz quadrada?
Sequências de Números, Figuras, Letras e Palavras
IBGP · 2024
Como verificar se um número inteiro n é primo usando o teste até a raiz quadrada?
Mostrar resposta e comentário
Resposta
Verifique todos os divisores inteiros de 2 até \(\lfloor\sqrt{n}\rfloor\); se nenhum dividir \(n\), então \(n\) é primo.Porque os fatores aparecem em pares, qualquer divisor não trivial \(d>1\) tem parceiro \(n/d\); assim, se existir um divisor, ao menos um deles é ≤ \(\sqrt{n}\).
É suficiente checar inteiros de 2 até \(\lfloor\sqrt{n}\rfloor\) (ou apenas os divisores primos nessa faixa) — se nenhum dividir \(n\), então não há fatores além de 1 e \(n\).
exemplo
Verificar \(n=47\):
\(\sqrt{47}\approx 6{,}855\), então checamos 2, 3 e 5 (primos ≤ 6).
\(47\div2=23{,}5\) → não divisível
\(47\div3\approx15{,}666\) → não divisível
\(47\div5=9{,}4\) → não divisível
Portanto 47 não tem divisores inteiros entre 2 e \(\lfloor\sqrt{47}\rfloor\), logo \(47\) é primo.
Veja como foi cobrado:
https://flashcardsconcursos.com.br/portal/flashcard/329423
Conteúdo do catálogo FC Concursos · Atualizado em