Bonsoir, mon algorithme de detection de nombre premiers n'est pas assez rapide à mon goût pouvez vous m'aiday à l'étoffer ? Qu'est ce qui va pas avec mon algo ?

from time import time
n=3
a=0
t=time()
i=2
p=[]
while n < 1000:
    for i in range(2,n):
        if n % i != 0:
            a+=1
        else:
            break
    if a == n-2:
        p.append(n)
    a=0
    n+=2
tt=time()
print(p)
f="\n"+str(len(p))+" prime numbers computed in "+(str(tt - t))+" seconds.\n"
print(f)
input()

Salut,

J'ai du mal à tout saisir dans ton algo.... Faudrait peut-être donner des noms de variables plus explicites...

Ta variable a par exemple... Bah même si elle est utile, elle a pas trop de sens.

Donc première simplification algorithmique que je proposerais :

Remplacer ta boucle principale :

while n < 1000:
    for i in range(2,n):
        if n % i != 0:
            a+=1
        else:
            break
    if a == n-2:
        p.append(n)
    a=0
    n+=2

Par :

for n in range(1000):
    for i in range(2,n):
        if n % i == 0:
            break
    else:
        p.append(n)

J'utilise la une structure spéciale propre à python : for.... else.
C'est à dire que le bloc suivant le mot-clé else ne sera exécuté qu'à condition que la boucle se finisse normalement ( et non par un break ).

Ça me semble être un peu meilleur pour la clarté de ton code et son volume... Mais niveau performances, ça ne doit pas changer grand chose.

( d'ailleurs en passant, j'ai pas compris pourquoi tu incrémentes n de 2 à chaque fois.... Ça doit être une propriété arithmétique que je ne connais pas...).

Et sinon une astuce bien bien plus intéressante pour augmenter drastiquement la vitesse d'exécution de ton code : tu peux te contenter de regarder si n est divisible par un des nombres entre 2 et sqrt(n).... Au dessus de la racine de ton nombre, c'est simplement les multiples " complémentaires " que tu trouveras.
Du coup, si le nombre est multiple avec aucun nombre inférieur à sa racine, alors il est premier... Je te laisse modifier ce qu'il faut en conséquence.

( ah et je tiens à préciser que je ne suis qu'en L1, donc ce que je dis est à prendre avec des pincettes, y a forcément moyen de faire un truc encore plus simple, mais je te montre déjà quelque chose de plus clair, plus propre, et plus performant si tu utilises l'astuce arithmétique que je t'ai donné )

déjà tu peux tester jusqu'à racine de n au lieu de n.

( d'ailleurs en passant, j'ai pas compris pourquoi tu incrémentes n de 2 à chaque fois.... Ça doit être une propriété arithmétique que je ne connais pas...).

2 est le seul nombre premier pair pour des raisons évidentes, donc pas la peine de tester les autres nombres pairs qui forcément auront pour diviseur au moins 2.

Après si tu veux aller plus loin, tu peux faire un truc comme ça : http://puu.sh/rzXPV/09cd37e9d5.pdf
pour améliorer encore un petit peu.

Le 06 octobre 2016 à 21:25:25 Asayakez a écrit :
déjà tu peux tester jusqu'à racine de n au lieu de n.

( d'ailleurs en passant, j'ai pas compris pourquoi tu incrémentes n de 2 à chaque fois.... Ça doit être une propriété arithmétique que je ne connais pas...).

2 est le seul nombre premier pair pour des raisons évidentes, donc pas la peine de tester les autres nombres pairs qui forcément auront pour diviseur au moins 2.

Après si tu veux aller plus loin, tu peux faire un truc comme ça : http://puu.sh/rzXPV/09cd37e9d5.pdf
pour améliorer encore un petit peu.

Ah oui je suis con, je me disais bien que c'était une histoire de parité, mais je réfléchissais à l'envers.......

Bref, je dois être fatigué.

Du coup merci pour l'info...

Tu peux gagner 150K dollar si tu trouves un nombre primaire avec 100 million de chiffres
https://www.eff.org/awards/coop

Sinon au lieu de tester tous les nombre de 2 à sqrt(n), vous pouvez vous limiter uniquement aux nombres premiers précédemment trouvés, puisque tout nombre entier non nul peut s'écrire sous la forme d'un produit de nombres premiers. Ça devrait faire moins de comparaisons.

Petite version récursive pour la forme.

def primes(n):
    if n == 2:
        return (2, )
    else:
        prev_primes = primes(n - 1)
        sqrt = n**0.5
        for p in prev_primes:
            if n % p == 0:
                return prev_primes
            if p > sqrt:
                return prev_primes + (n, )

Mais le "mieux" (rapide et simple) reste le crible d’Ératosthène pour générer les nombres premiers jusqu'à n.