Codigo demasiado lento para numero perfeito

[andfernandes]

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

[vbmaster]

Tal como a obtenção de números primos se torna um processo lento para número muito grandes (não é por acaso que há superpc's a correrem programas desses) também este que é do mesmo género deve ficar.

[David Pintassilgo]

A ideia seria reduzir o trabalho ao PC, mas nesse caso não sei se daria para fazer isso.

[andfernandes]

Sao capazes de terem razao..tambem axo k sim...obrigados na mesma

[TheDark]

Além de que, se pretendes rapidez, Visual Basic não é a linguagem mais adequada. Nem de longe :😁

[José Oliveira]

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.

[GoncaloMendes]

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  😕