Check Prime Number

Q: Qual é a complexidade de tempo para verificar se um número é primo?

A divisão por tentativa até √n leva tempo O(√n) e espaço O(1) . Para n até 2^31-1 , isso representa no máximo cerca de 46,000 divisões, ou 23,000 quando você ignora os divisores pares. Testar todos os divisores até n-1 é O(n) , cerca de dois bilhões de etapas para a maior entrada.

Q: Por que você verifica os divisores apenas até a raiz quadrada de n?

Os divisores vêm em pares d e n / d , cujo produto é n . Se ambos fossem maiores que √n , o produto seria maior que n . Portanto, todo par tem um elemento menor ou igual a √n e, se nenhum divisor aparecer até então, n é primo.

Q: 1 é um número primo?

Não. Um número primo tem exatamente dois divisores diferentes, 1 e ele mesmo, e 1 tem apenas um. Deixar 1 de fora mantém única a fatoração de todo número inteiro em números primos. É por isso que isPrime(1) retorna false .

Q: Existe uma maneira mais rápida de testar se números muito grandes são primos?

Para um número de 32 bits, a divisão por tentativa até √n é rápida o suficiente. Para números com dezenas de dígitos, os programas usam o teste de Miller-Rabin, que verifica algumas potências modulares em vez de testar divisores. Para listar todos os números primos até um limite, o Crivo de Eratóstenes é melhor do que testar cada número individualmente.

InicianteMatemática e simulação

+10

Um número primo é um número inteiro maior que 1 cujos únicos divisores são 1 e ele mesmo. Você recebe um número inteiro positivo n. Retorne true se n for primo e false caso contrário. O número 1 não é primo.

Função

isPrime(n: integer) → boolean

ninteger: o número inteiro positivo a ser testado
Retornaboolean: verdadeiro se n for primo, falso caso contrário

Restrições

1 ≤ n ≤ 2³¹ - 1

Exemplos

Entrada: n = 29
Saída: true
Explicação: Nenhum de 2, 3, 4 ou 5 divide 29, e 6 × 6 = 36 já ultrapassa 29, então não resta nenhum divisor a encontrar. 29 é primo.

Entrada: n = 1
Saída: false
Explicação: Um número primo tem exatamente dois divisores, 1 e ele mesmo. 1 tem apenas um divisor, então a resposta é false.

Entrada: n = 91
Saída: false
Explicação: 91 parece primo, mas 7 × 13 = 91. O divisor 7 aparece antes que a busca passe de √91 ≈ 9.5.

+15 testes ocultos ao enviar

Para ir além

Todo número primo maior que 3 tem a forma 6k-1 ou 6k+1. Você consegue usar isso para testar apenas um terço dos divisores candidatos?

Dicas

Abra uma de cada vez. Cada uma revela um pouco mais.

0 de 3 abertas

Solução

A definição diz para descartar todos os divisores de 2 a n-1, e, para a maior entrada que é um número primo, isso representa mais de dois bilhões de divisões. Os divisores vêm em pares cujo produto é n, e o menor de cada par é no máximo √n. Portanto, você só precisa pesquisar até √n, no máximo cerca de 23,000 candidatos ímpares.

Tente cada divisor

Correta, mas não termina nos maiores testes

Intuição

A definição fornece o algoritmo. Um número n ≥ 2 é primo quando nenhum dos números de 2, 3, ..., n-1 o divide. Teste cada candidato d com n % d == 0 e retorne false no primeiro que o dividir. Para 91, o laço testa de 2 até 6 e para em 7.

Trate n < 2 primeiro. Para n = 1, o intervalo de candidatos está vazio, então o laço nunca encontraria um divisor e consideraria 1 primo.

Números compostos geralmente param cedo, mas um número primo passa por todos os testes, então o laço vai até o fim. Para n = 2147483647, que é primo, isso representa cerca de 2.1 × 10^9 divisões, muito mais do que alguns segundos permitem.

Algoritmo

Se n < 2, retorne false.
Percorra d de 2 até n-1.
Se n % d == 0, retorne false.
Após o loop, retorne true.

def isPrime(n):
    if n < 2:
        return False
    for d in range(2, n):
        if n % d == 0:
            return False
    return True

Divisão por tentativa até a raiz quadrada

Intuição

Os divisores vêm em pares. Se d divide n, então n / d também divide, e os dois se multiplicam para resultar em n. Eles não podem ser ambos maiores que √n, pois então o produto seria maior que n. Portanto, se n tiver algum divisor além de 1 e dele mesmo, terá um que é menor ou igual a √n. Para 91, o par é 7 e 13, e 7 ≤ 9.5. Se nenhum número até √n dividir n, nenhum número acima dele também dividirá.

Escreva o limite como d * d ≤ n em vez de chamar uma função de raiz quadrada. Assim, tudo permanece em números inteiros, sem arredondamento. O sinal de igualdade importa: 49 = 7 × 7, e seu único divisor 7 fica exatamente em √49.

Você também pode pular metade dos candidatos. Trate 2 separadamente: um n par só é primo quando é 2. Depois disso, um n ímpar só tem divisores ímpares, então comece em 3 e avance de 2 em 2. Para n = 2147483647, o loop agora executa cerca de 23,000 vezes em vez de 2.1 × 10^9.

Algoritmo

Se n < 2, retorne false.
Se n for par, retorne se n == 2.
Inicie d em 3 e faça um loop enquanto d * d ≤ n, usando um tipo de 64 bits para d.
Se n % d == 0, retorne false. Caso contrário, some 2 a d.
Após o loop, retorne true.

def isPrime(n):
    if n < 2:
        return False
    if n % 2 == 0:
        return n == 2  # 2 is the only even prime
    d = 3
    while d * d <= n:
        if n % d == 0:
            return False
        d += 2
    return True

Armadilhas e casos extremos

A ideia cabe em uma linha. Os bugs aparecem nos limites: as menores entradas e o último divisor.

Retornar true para 1. Ele tem um divisor, não dois, então não é primo.
Rejeitar 2 porque é par. Verifique n == 2 antes de descartar os números pares.
Repetir o laço enquanto d * d < n em vez de ≤. Assim, quadrados de números primos, como 9, 49 e 2147117569 = 46337², são considerados primos.
Estouro em d * d. Em um int de 32 bits, 46341 × 46341 = 2147488281 não cabe e sofre overflow, tornando-se um número negativo; assim, o teste continua passando e o laço vai muito além de √n. Use um tipo de 64 bits para d ou compare d ≤ n / d.
Obter o limite de um sqrt de ponto flutuante e truncá-lo. Um double é exato para todos os valores de n neste caso, mas, para entradas de 64 bits, o arredondamento pode resultar em um valor uma unidade abaixo da raiz verdadeira e ignorar o único divisor que importa. d * d ≤ n não apresenta esse risco.

Perguntas frequentes4

Qual é a complexidade de tempo para verificar se um número é primo?

A divisão por tentativa até √n leva tempo O(√n) e espaço O(1). Para n até 2^31-1, isso representa no máximo cerca de 46,000 divisões, ou 23,000 quando você ignora os divisores pares. Testar todos os divisores até n-1 é O(n), cerca de dois bilhões de etapas para a maior entrada.

Por que você verifica os divisores apenas até a raiz quadrada de n?

Os divisores vêm em pares d e n / d, cujo produto é n. Se ambos fossem maiores que √n, o produto seria maior que n. Portanto, todo par tem um elemento menor ou igual a √n e, se nenhum divisor aparecer até então, n é primo.

1 é um número primo?

Não. Um número primo tem exatamente dois divisores diferentes, 1 e ele mesmo, e 1 tem apenas um. Deixar 1 de fora mantém única a fatoração de todo número inteiro em números primos. É por isso que isPrime(1) retorna false.

Existe uma maneira mais rápida de testar se números muito grandes são primos?

Para um número de 32 bits, a divisão por tentativa até √n é rápida o suficiente. Para números com dezenas de dígitos, os programas usam o teste de Miller-Rabin, que verifica algumas potências modulares em vez de testar divisores. Para listar todos os números primos até um limite, o Crivo de Eratóstenes é melhor do que testar cada número individualmente.

Python

def isPrime(n):
    # Escreva o código aqui

Casos de teste

Caso 1

Caso 2

Caso 3

Entrada

n = 29

Esperado

true