Perfect Number

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

Encontrar pares de divisores até √n leva tempo O(√n) e espaço O(1) . Para n = 10^8 , isso corresponde a cerca de 10^4 etapas. Testar cada candidato até n / 2 leva O(n) , cerca de 5 × 10^7 etapas para a mesma entrada.

Q: Quantos números perfeitos existem abaixo de 10^8?

Cinco: 6 , 28 , 496 , 8128 e 33550336 . Eles ficam raros rapidamente. O próximo, 8589869056 , nem cabe em um inteiro de 32 bits.

Q: Existem números perfeitos ímpares?

Ninguém sabe. Todo número perfeito encontrado até agora é par. As buscas descartaram números perfeitos ímpares menores que 10^1500 , mas nenhuma prova afirma que eles não possam existir. Sua função precisa funcionar com base na definição, não em um palpite de que a entrada é par.

Q: Qual é a diferença entre números perfeitos, abundantes e deficientes?

Compare a soma dos divisores próprios com o número. Se forem iguais, o número é perfeito, como 28 . Se a soma for maior, o número é abundante, como 12 , cujos divisores somam 16 . Se for menor, o número é deficiente, como todo número primo, cujo único divisor próprio é 1 .

InicianteMatemática e simulação

+10

Um divisor próprio de n é um divisor positivo menor que o próprio n. Um número perfeito é igual à soma de seus divisores próprios: 6 = 1 + 2 + 3. Você recebe um inteiro positivo n. Retorne true se n for perfeito e false caso contrário.

Função

isPerfect(n: integer) → boolean

ninteger: o inteiro positivo a ser testado
Retornaboolean: verdadeiro se n for igual à soma de seus divisores próprios, falso caso contrário

Restrições

1 ≤ n ≤ 10⁸

Exemplos

Entrada: n = 28
Saída: true
Explicação: Os divisores próprios de 28 são 1, 2, 4, 7 e 14. Eles somam 28, então 28 é perfeito.

Entrada: n = 12
Saída: false
Explicação: Os divisores próprios de 12 são 1, 2, 3, 4 e 6. A soma deles é 16, que ultrapassa 12.

Entrada: n = 1
Saída: false
Explicação: 1 não tem nenhum divisor próprio, então a soma é 0, não 1.

+16 testes ocultos ao enviar

Para ir além

Todo número perfeito par tem a forma 2^(p-1) × (2^p-1), em que 2^p-1 é primo. Você consegue listar todos os números perfeitos menores que 10^8 usando essa fórmula, sem testar cada número?

Dicas

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

0 de 3 abertas

Solução

A definição pede uma soma de divisores, e o loop óbvio testa cada candidato até n / 2. Para n = 10^8, isso representa 5 × 10^7 divisões. Os divisores vêm em pares cujo produto é n, então você pode coletar os dois membros de cada par enquanto pesquisa apenas até √n, cerca de 10^4 etapas.

Some todos os divisores próprios

Correta, mas não termina nos maiores testes

Intuição

Siga a definição. Experimente cada d começando por 1 e, quando n % d == 0, adicione d a um total acumulado. No final, compare o total com n. Para 28, o loop encontra 1, 2, 4, 7 e 14, e 1 + 2 + 4 + 7 + 14 = 28.

Você pode parar em n / 2. Um divisor diferente de n deixa um quociente de pelo menos 2, então nunca é maior que a metade de n. Esse limite também funciona para n = 1: o loop executa zero vezes, o total permanece 0 e a resposta é false.

Reduzir o intervalo pela metade não altera o crescimento. Para n = 10^8, o loop ainda executa 5 × 10^7 vezes, e isso acontece para toda entrada desse tamanho, seja ela divisora ou não.

Algoritmo

Defina total como 0.
Percorra d de 1 até n / 2.
Se n % d == 0, adicione d a total.
Retorne se total == n.

def isPerfect(n):
    total = 0
    # No proper divisor of n is larger than n / 2.
    for d in range(1, n // 2 + 1):
        if n % d == 0:
            total += d
    return total == n

Coletar pares de divisores até a raiz quadrada

Intuição

Quando d divide n, n / d também divide n. Para 28, os pares são 1 × 28, 2 × 14 e 4 × 7. Em cada par, um dos membros é no máximo √n, porque dois números maiores que √n multiplicados resultam em mais que n. Portanto, uma busca até √n encontra cada par uma vez, e você soma os dois membros à medida que avança.

Dois membros exigem cuidado. O par 1 × n inclui o próprio n, que não é um divisor próprio: comece o total em 1 e a busca em 2. Esse início está errado para n = 1, cujo único divisor é ele mesmo, então retorne false para esse caso primeiro. E, quando n é um quadrado perfeito, a raiz forma um par consigo mesma: para 36, 6 × 6 deve somar 6 uma vez, não duas.

Escreva o limite como d * d ≤ n, que mantém os cálculos em números inteiros. Para n = 10^8, o loop para em d = 10^4, então executa cerca de 10^4 vezes em vez de 5 × 10^7.

Algoritmo

Se n == 1, retorne false.
Defina total como 1 e d como 2.
Enquanto d * d ≤ n: se d divide n, some d e some também n / d quando for diferente de d.
Passe para o próximo d.
Retorne se total == n.

def isPerfect(n):
    if n == 1:
        return False
    total = 1  # 1 divides every n > 1; n itself does not count
    d = 2
    while d * d <= n:
        if n % d == 0:
            total += d
            partner = n // d
            if partner != d:  # a square root pairs with itself: add it once
                total += partner
        d += 1
    return total == n

Armadilhas e casos extremos

O truque dos pares é curto, e cada um de seus bugs altera a soma em exatamente um divisor.

Contar o próprio n. O par 1 × n adiciona n, e então todo número parece ter uma soma maior que n. Comece o total em 1 e a busca em 2.
Considerar 1 perfeito. Com o total iniciado em 1, a entrada 1 resulta na comparação 1 == 1. A soma de seus divisores próprios é 0, então trate esse caso antes do loop.
Adicionar uma raiz quadrada duas vezes. Para 16, os divisores próprios são 1, 2, 4 e 8, cuja soma é 15. Adicionar 4 duas vezes resulta em 19.
Parar em d * d < n. Isso ignora completamente a raiz quadrada, então 4 em 16 nunca é contado.
Obter o limite a partir de uma raiz quadrada de ponto flutuante. Em precisão simples, ou acima de 2^53 em precisão dupla, o resultado da raiz de um quadrado perfeito pode ficar uma unidade abaixo do valor correto e deixar de incluir um divisor. O teste d * d ≤ n usa apenas números inteiros e nunca tem esse problema.

Perguntas frequentes4

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

Encontrar pares de divisores até √n leva tempo O(√n) e espaço O(1). Para n = 10^8, isso corresponde a cerca de 10^4 etapas. Testar cada candidato até n / 2 leva O(n), cerca de 5 × 10^7 etapas para a mesma entrada.

Quantos números perfeitos existem abaixo de 10^8?

Cinco: 6, 28, 496, 8128 e 33550336. Eles ficam raros rapidamente. O próximo, 8589869056, nem cabe em um inteiro de 32 bits.

Existem números perfeitos ímpares?

Ninguém sabe. Todo número perfeito encontrado até agora é par. As buscas descartaram números perfeitos ímpares menores que 10^1500, mas nenhuma prova afirma que eles não possam existir. Sua função precisa funcionar com base na definição, não em um palpite de que a entrada é par.

Qual é a diferença entre números perfeitos, abundantes e deficientes?

Compare a soma dos divisores próprios com o número. Se forem iguais, o número é perfeito, como 28. Se a soma for maior, o número é abundante, como 12, cujos divisores somam 16. Se for menor, o número é deficiente, como todo número primo, cujo único divisor próprio é 1.

Python

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

Casos de teste

Caso 1

Caso 2

Caso 3

Entrada

n = 28

Esperado

true