Jump to content

Codigo demasiado lento para numero perfeito


andfernandes

Recommended Posts

Boa tarde! eu tenho de desenvolver um programa pa verificar se um numero é perfeito... o problema é k eu ja consegui gerar esse codigo mas se for pa numeros muito elevados o programa fica parado nao se mexe.poderiam me ajudar tentando arranjar um metodo mais rapido e pratico de fazer isto.. apresento o codigo pa o calculo dos numeros perfeitos

NUMERO PERFEITO: Em Matemática, um número perfeito é um número inteiro no qual, a soma de todos os seus divisores positivos próprios (excluindo ele mesmo) é igual ao próprio número.

   

Function numeroPerfeito(ByVal num As Integer)
        soma = 0
        Dim i, k, par As Integer
        For i = 1 To num - 1        ' ciclo para encontrar os divisores do numero
            If (num Mod i) = 0 Then ' verifica se o numero a dividir pela variavel do ciclo i apresenta resto 0 se sim esse valor é um divisor do numero
                soma += i
            End If
        Next
        Dim val As Integer
        For i = 1 To num - 1    ' ciclo para encontrar os numeros perfeitos anteriores ao numero lido
            val = num - i
            par = 0
            For k = 1 To val - 1
                If (val Mod k) = 0 Then
                    par += k
                End If
            Next
            If (par = val) Then
                valores += val & " "
            End If
        Next
    End Function
Link to comment
Share on other sites

Talvez ajudem os seguintes links:

http://mathforum.org/dr.math/faq/faq.perfect.html#computer

http://mathforum.org/library/drmath/view/55841.html

Deste último retiro o seguinte (repara no método sugerido no 3º parágrafo):

One way to find out if a number X is perfect is to find its

factorization into prime powers, make a list of all the divisors using

that, add them up, and compare to X. If you get equality, X is

perfect. If the sum exceeds X, it is called "abundant," and if the sum

is smaller than X, it is called "deficient."

This method could be very lengthy if X is extremely large! You will

need a factoring subroutine and a prime-testing subroutine, as well as

the usual arithmetic. Is there a limit on the size of X?  Perhaps X is

restricted to single-precision or double-precision integers?

Another way is to use the fact that there is no odd perfect number

with less than 200 decimal digits, and all the even perfect numbers

have the special form 2^(n-1)*(2^n-1), where 2^n-1 is a prime number

(called a Mersenne prime). If X has less than 200 decimal digits, n

can have any of the following values: 2, 3, 5, 7, 13, 17, 19, 31, 61,

89, 107, 127, 521, or 607, and no others. Take the number X and

divide out as large a power of 2 as you can, 2^k = p, so X/p is odd. 

If k+1 is not on the list, then X is not perfect. If k+1 is on that

list, and X/p = 2*p - 1, then X is perfect, but if X/p has any other

value, X is not perfect. If X has more than 200 digits and is even,

the list can be extended, but if it is odd, you probably cannot deal

with the problem this way.

Link to comment
Share on other sites

  • 3 years later...

esse processo, tal como a obtenção de numeros primos, pode ser bastante acelarada, passo a explicar

Se o número final é "num"

e num mod 2=0 entao num mod (num/2)=0 também, logo o ciclo basta ser feito para num/2

Se num mod [número muito grande]=0 segue-se a mesma lógica, e divide-se em muito o indice final do ciclo, este processo consegue acelarar em muito testes de primos e números perfeitos.

VB consegue com este método lidar muito bem com números grandes, desde que por grandes entendam no máximo números de 64-bits  😕

Link to comment
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
×
×
  • Create New...

Important Information

By using this site you accept our Terms of Use and Privacy Policy. We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.