[Mini-Challenge Basic #6] : Nombres parfaits

[pierrotdu18]

Voilà ma participation

Code: Select all

Define isPerfect(n)=
Func
Local r,k,t
r:=0
t:=n-2
For k,1,t
  If mod(n,k)=0
    r:=r+k
EndFor
Return r=n
EndFunc

[davidElmaleh]

Pour avoir un aperçu pour la dernière participation de pierrotdu18 :
isperfect(10^6) = false en 6 sec. 63
isperfect(2*10^6) = false en 12 sec. 94

[Adriweb]

Et pour info, si je n'étais pas parti sur un truc court, j'aurais fais en gros la même chose que ce que pierrot vient de proposer
(Algo standard, cf. RosettaCode )

Edit : avec le check de parité en plus dès le début, pour la vitesse

[pierrotdu18]

Je suis flatté

[davidElmaleh]

Mon code est dans le même esprit que celui de pierrotdu18 :

• variable de somme
• boucle for dans laquelle on recherche et on somme les diviseurs de n
• sortie et vérification

Mais il est implémenté (petite astuce : comment rechercher les diviseurs d'un nombre? )

[davidElmaleh]

Nouvelles statistiques :
pour ma part, j'arrive à :
isperfect(10^20) = false en 2 secondes
isperfect(10^25) = false en 5 secondes 30
isperfect(2658455991569831744654692615953842176) = true en moins 30 ms!

[pierrotdu18]

Bah écoute, propose nous ta réponse

[Bisam]

Bon, voici ma mouture...
Pour éviter les désagréments de non simplification des "floor(sqrt(n))" lorsque n est trop grand, je me suis fait ma propre fonction qui calcule la racine carrée entière d'un nombre.

Code: Select all

Define Libpub intsqrt(n)=
Local q,r,l,i,j,k,u,res
q := n
l := {}
While q>0
  l := augment({mod(q,100)},l)
  q := intDiv(q,100)
EndWhile
k := dim(l)
j := 1
r := 0
res := 0
For i,1,k
  r := 100*r + l[i]
  u := 0
  While r≥j
    r := r-j
    j := j+2
    u := u+1
  EndWhile
  j := 10*j - 9
  res := 10*res + u
EndFor
EndFunc

Ensuite, le code de la fonction en elle-même :

Code: Select all

Define isperfect(n)=
Func
Local i,k,p,r,res
p := 2n
k := 2
While mod(n,2)=0
  n := shift(n)
  k := 2k
EndWhile
res := k-1
r := intsqrt(n)+1
i := 3
While i < r
  k := 1
  While mod(n,i)=0
    n := n/i
    k := i*k+1
  EndWhile
  If k > 1 Then
    res := res * k
    r := intsqrt(n) + 1
  EndIf
  i := i+2
EndWhile
If n > 1
  res := res*(n + 1)
Return(res=p)
EndFunc

[pierrotdu18]

Bisam, pourquoi pour le intsqrt(), tu n'appliques juste pas la fonction

$mathjax$\dfrac12\left(x+\dfrac2x\right)$mathjax$

4 ou 5 fois pour le ceiler après?...

EDIT: Oups je me suis trompé de fonction mais bon tu vois bien celle dont je veux parler

[Bisam]

Essaie... tu verras que c'est en fait (en moyenne, et pour des nombres suffisamment grands) beaucoup plus lent d'utiliser l'algorithme de Héron que tu cites (bien qu'il converge très rapidement).
En effet, le facteur limitant est cette fois-ci la division de réels.
En plus, il y a toujours les problèmes d'approximation qui font qu'on n'obtient pas forcément le bon résultat !