Flashcard FC437251
Qual o método prático para verificar se um número inteiro n (>1) é primo?
Conjuntos
IDCAP · 2024
Qual o método prático para verificar se um número inteiro n (>1) é primo?
Mostrar resposta e comentário
Resposta
Testar divisibilidade apenas pelos números primos menores ou iguais a \( \sqrt{n} \); se nenhum dividir, n é primo.Explicação:
Se n tiver um divisor d distinto de 1 e n, então existe outro divisor \(d'\) tal que \(d\cdot d'=n\).
Um dos dois divisores será ≤ \( \sqrt{n} \), portanto basta testar divisibilidade por primos ≤ \( \sqrt{n} \).
Exemplo:
Verificar se 101 é primo:
\( \sqrt{101}\approx 10{,}05 \), testar primos 2, 3, 5, 7.
\(101\mod2=1,\;101\mod3=2,\;101\mod5=1,\;101\mod7=3\).
Nenhum divide 101, logo 101 é primo.
Veja como foi cobrado:
https://flashcardsconcursos.com.br/portal/flashcard/437146
Conteúdo do catálogo FC Concursos · Atualizado em