Warning: Undefined array key -1 in /home/clients/a4e6fc1ce1761b72982b805de0f418c4/web/python/mesrecettespython/inc/html.php on line 1458

Différences

Ci-dessous, les différences entre deux révisions de la page.

Lien vers cette vue comparative

--- est_premier [2009/01/03 11:45]
tyrtamos
+++ est_premier [2011/03/25 15:02]
tyrtamos
@@ Ligne 21: / Ligne 21: @@
 La fonction renvoie "True" si le nombre donné est premier, et "False" dans le cas contraire.
-Petit complément ici, on a une fonction "racine carrée de ...". Mais cette racine carrée nécessiterait normalement l'utilisation de la fonction sqrt() du module math, qui entrainerait une conversion du nombre en flottant, alors qu'on est ici avec des entiers, et éventuellement des entiers très long. Alors, nous ajoutons une fonction "lsqrt(n)" qui calcule la racine carrée entière de n'importe quel nombre entier, y compris très long (10000 chiffres si vous voulez) sans nécessiter de conversion avec des flottants.
+Petit complément ici, on a une fonction "racine carrée de ...". Mais cette racine carrée nécessiterait normalement l'utilisation de la fonction sqrt() du module math, qui entrainerait une conversion du nombre en flottant, alors qu'on est ici avec des entiers, et éventuellement des entiers très long. Alors, nous utilisons une fonction "lsqrt(n)" qui calcule la racine carrée entière de n'importe quel nombre entier, y compris très long (10000 chiffres si vous voulez) sans nécessiter de conversion avec des flottants: cette fonction est décrite sur ce présent site ici: [[http://python.jpvweb.com/mesrecettespython/racine_entiere]].
 <code python>
-# =============================================================================
-def lsqrt(x,n=2):
-    """racine (carrée si n=2) entière d'un nombre entier éventuellement très long"""
-    if x<2:
-        if x==1:
-            return 1
-        else:
-            return 0
-    i, j = 1, x
-    while i!=j:
-        k=(i+j)//2
-        if k**n>x:
-            j=k
-        else:
-            i=k+1
-    if x-k**n<0:
-        return k-1
-    return k
-# =============================================================================
 def estpremier(n):
     """estpremier(n): dit si un nombre est premier (renvoie True ou False)"""
@@ Ligne 56: / Ligne 36: @@
     # autres cas
     k=3
-    r=lsqrt(n)+1
+    r=lsqrt(n)
     while k<=r:
         if n % k == 0:
@@ Ligne 71: / Ligne 51: @@
 </code>
-Cas particulier: même si ça a un petit côté artificiel, le nombre 1 n'est pas premier: la fonction estpremier(1) renvoie donc False.
+Cas particulier: même si ça a un petit côté artificiel, la définition dit que le nombre 1 n'est pas premier: la fonction estpremier(1) renvoie donc False.
 Vous pouvez tester cette fonction avec la Calculext ici: [[http://calculext.jpvweb.com]]
@@ Ligne 129: / Ligne 109: @@
 #  Test de primalité probabiliste de Miller-Rabin
 def _millerRabin(a, n):
+    """Ne pas appeler directement (fonction utilitaire). Appeler millerRabin(n, k=20)"""
     # trouver s et d pour transformer n-1 en (2**s)*d
     d = n - 1

Les recettes Python de Tyrtamos

Outils pour utilisateurs

Outils du site

Différences

Outils de la page