Discussion :

[Fawn_noOb_wxPython]

Bonsoir, voici mon problème:

Je dois écrire un algo qui me permette d'afficher dans un tableau les nombres premiers dans un intervalle définit par start et stop, cependant je n'arrive à isoler que les impairs....J'ai eu beau lire des algo de maths etc....Je n'arrive pas à comprendre ce qu'il me manque comme test pour sortir les bonnes valeurs !

Voici où j'en suis :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
 
def nbPremier(start,stop):
    i=start
    tab=[]
    j=0
    while i<=stop:
        if i%2!=0 and i!=1 or i==2: #cas particuliers
            tab.append(i)
        i+=1        
    while j<len(tab)-1:
        print tab[j]
        j+=1
 
    print tab,len(tab)
 
nbPremier(1,100)

Je vous remercie d'avance

[wiztricks]

Je n'arrive pas à comprendre ce qu'il me manque comme test pour sortir les bonnes valeurs !

Il manque le test pour savoir si le nombre est premier ou pas. Mais je ne vais pas gâcher le plaisir qu'aura Tyrtamos à vous raconter çà en long en large et en travers.

- W

[tyrtamos]

Bonjour,

Voilà que wiztricks me présente comme un maniaque des nb premiers... mais c'est vrai que c'est amusant

Pour qu'un nombre n soit premier, il faut:

- qu'il soit impair (à part 2 qui est le seul nombre pair qui soit premier)

- qu'il ne soit divisible par aucun nombre impair situé de 3 à racine carrée de n. En effet, si on n'a pas trouvé de diviseur avant racine de n, on n'en trouvera plus après!

Voilà un petit code commenté qui fait ça:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
from math import sqrt
 
def premiers(deb, fin):
    """Retourne la liste des nombres premiers entre deb et fin
       par la méthode des divisions
    """
    p = []
    n = deb
    if n<2:
        n = 2 # pas de nb premier en dessous de 2
    if n%2==0:
        # n est pair
        if n==2:
            p.append(2) # 2 est le seul nb pair premier
        n += 1 # on fait que n soit impair
    while n<fin:
        rac = int(sqrt(n)) # limite sup des diviseurs i = racine de n
        i = 3 # diviseur initial
        okprem = True # drapeau pour signaler un nb premier
        while i<=rac:
            if n%i==0:
                okprem = False # n divisible par i => il n'est pas premier
                break # on sort de la boucle while
            i += 2 # diviseur impair suivant
        if okprem:
            # aucune division exacte n/i: n est premier
            p.append(n)    
        n += 2 # nb impair suivant
    return p # retour de la liste des nb premiers trouvés

Pour le calcul de la racine carrée, on a utilisé la fonction sqrt du module math qui calcule en virgules flottantes, mais pour la beauté du code, on pourrait calculer directement la racine carrée ENTIERE grâce à l'algorithme de Héron d'Alexandrie (un algo qui a 2000 ans: waouh!)

Application:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
print(premiers(2,100))
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]
 
print(premiers(20,100))
[23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]

Et avec premiers(2, 1000000), on trouve les 78498 nombres premiers inférieurs à 1 million en 5 secondes environ.

Si le nombre de départ (deb) était toujours égal à 2, on pourrait améliorer la vitesse de calcul en utilisant les nombres premiers déjà trouvés avant comme diviseurs, au lieu de tous les nombres impairs. En effet, prendre tous les nombres impairs comme diviseur fait que, par exemple, on essaie 3, puis 5, puis... 15. Mais si ni 3 ni 5 n'ont marché, l'essai de 15 est inutile.

Et il y a des algorithmes plus efficaces pour faire tout ça, par exemple le "crible d'Eratosthène", mais le code est plus compliqué. Un essai que j'avais fait m'a permis de trouver les 455.052.511 nombres premiers inférieurs à 10 milliard en une heure environ, ce qui correspond à un fichier de plus de 5Go...

Bon courage!

[Fawn_noOb_wxPython]

Super, bien expliqué, que dire ? parfait et merci beaucoup !!!

[VinsS]

Bonjour,

...
- qu'il ne soit divisible par aucun nombre impair situé de 3 à racine carrée de n.

Qu'il ne soit divisible par aucun nombre premier situé de 3 à racine carrée de n.

Donc il faut puiser les diviseurs dans la liste qui se construit au fur et à mesure.


Edit: En fouillant au grenier, j'ai retrouvé ceci:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
 
from math import sqrt
 
primes = [3, 5, 7, 11]
num = 13
 
while num < 1000000:
    max_ = sqrt(num)
    counter = 0
    while primes[counter] < max_:
        prime = num
        if not num % primes[counter]:
            prime = 0
            break
 
        counter += 1
 
    if prime:
        primes.append(prime)
 
    num += 2
 
print("%s nombres premiers" % len(primes)) # --> 78663 nombres premiers

[tyrtamos]

Bonjour VinsS,

J'ai abordé ce point dans mon message. Si la question est: "trouver les nombres premiers inférieurs à n", il est évident qu'on doit utiliser les nombres premiers précédemment calculés comme diviseurs pour trouver le suivant.

Mais ce n'est pas la question posée qui est : "trouver les nombres premiers situés entre start et end". Dans ce cas, démarrer la recherche par le calcul de tous les nombres premiers inférieurs à start n'est pas forcément une bonne solution.

En fait, ça dépend des nombres start et end. Si on cherche entre 100 et 1000, il faut utiliser les nombres premiers comme diviseurs (et donc commencer par les calculer pour <100), mais si on cherche entre 10000 et 10500, je n'en pas sûr du tout: il faudrait faire la comparaison.

Si on connaissait les limites entre les 2 solutions, on pourrait avoir une fonction qui bascule d'une solution à l'autre en fonction des arguments. Mais ça complique sérieusement le code...

On pourrait aussi avoir une "réserve" de nombres premiers (par exemple les 1000 premiers) pour accélérer la plupart des calculs, et continuer avec les nombres impairs si ça ne suffit pas.

A noter que quand on augmente le nombre de nombres premiers à conserver en mémoire, il vient une limite qui est celle de la mémoire RAM. Pour augmenter ce nombre, il m'est déjà arrivé d'utiliser le module bitarray pour distinguer les nombres premiers (bit=1) des autres (bit=0). Cela marche très bien mais il faut s'accrocher pour le code...

[tyrtamos]

Petit complément à mon message précédent.

Voilà un petit code qui calcule les nombres premiers inférieurs à un nombre donné n, en utilisant pendant le calcul les nombres premiers déjà trouvés comme diviseurs:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
def premiers2(n):
    """Retourne la liste des nombres premiers <= n (méthode des divisions)
       On utilise les nb premiers déjà trouvés comme diviseurs
    """
    if n<2:
        return [] # pas de nb premier en dessous de 2
    if n==2:
        return [2]
    p = [2]
 
    k = 3 # 1er nb à tester
    while k<=n:
        rac = int(sqrt(k))
        i = 1 # indice initial de p (on ne tient pas compte de p[0]=2)
        okprem = True
        while i<len(p):
            if p[i]>rac:
                # k est premier!
                break # on sort de la boucle while i
            if k % p[i] == 0:
                # k n'est pas premier
                okprem = False
                break # on sort de la boucle while i
            i += 1 # indice suivant de p
        if okprem:
            p.append(k)
        k += 2 # nombre impair suivant à essayer
    return p

Faisons quelques comparaisons:

pour n = 100 000 (=> 9592 nb premiers), cette dernière solution donne à peu près le même temps de calcul (0.2s)

pour n = 1 million (=> 78498 nb premiers), cette dernière solution permet de gagner environ 20% du temps (4s au lieu de 5s)

pour n = 10 millions (=> 664579 nb premiers), cette dernière solution permet de gagner environ 45% de temps (80s au lieu de 145s)

On voit bien que l'avantage de temps augmente avec n, ce qui est logique!

Il resterait à faire des comparaisons en fonction des arguments start et end pour sélectionner le meilleur basculement entre les 2 méthodes...

[VinsS]

Avec mon code je n'obtiens pas les mêmes résultats:

n = 100.000 --> 9654
n = 1.000.000 --> 78663
n = 10.000.000 --> 665022

... ?

[tyrtamos]

Mes résultats sont conformes avec d'autres sites web comme:

http://villemin.gerard.free.fr/Wwwgv...r/quantite.htm

Et il y a des listes importantes ici:

http://nombrespremiersliste.free.fr/

[VinsS]

Comme j'avais des temps beaucoup plus longs que toi j'ai simplifié le code.

J'ai diminué le temps par deux mais j'ai toujours le même nombre de nombres premiers

100.000 --> 9654 nombres premiers at 0.360154390335083 sec.
1000.000 --> 78663 nombres premiers at 6.4767186641693115 sec.
10.000.000 --> 665022 nombres premiers at 145.63753271102905 sec.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
 
from math import sqrt
import time
 
primes = [3, 5, 7, 11]
num = 13
 
start = time.time()
while num < 10000000:
    max_ = sqrt(num)
    for p in primes:
        if p <= max_:
            if not num % p:
                break
 
        else:
            primes.append(num)
            break
 
    num += 2
 
end = time.time() - start
print("%s nombres premiers at %s" % (len(primes), end))

Oups, c'est if p <= max_: et non pas if p < max_:Maintenant j'ai les mêmes quantités de nombres que toi.

[tyrtamos]

Passe-moi ta liste pour 100.000 (avec fichier texte en pièce jointe), et je ferai demain matin une comparaison, avec un test de primalité pour les nombres qui ne se trouvent que dans l'une des listes.

[edit] ok, j'ai vu le oups...

[marco056]

Si cela peut aider :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def premier6(n):
	liste=[]
	premiers = [x for x in range(0,n)]
	for i in range(2,int(n**0.5)):
		for j in range(2*i, n, i):
			premiers[j]=0
	premiers[1]=0
	for j in premiers:
		if premiers[j] != 0:
			liste.append(j)
	return(liste, len(liste))
 
print(premier6(1000000))
 
import timeit
duree61 = timeit.Timer(stmt='premier6(1000000)', setup='from __main__ import premier6')
print (duree61.timeit(number=1))

0.68s pour 78498 nombres premiers.

[tyrtamos]

Bonjour marco056,

Merci pour le code: il s'agit ici du crible d’Ératosthène, dont j'avais bien dit qu'il était plus efficace. Mais je le trouve un peu plus difficile à comprendre que la méthode des divisions.

Et il est limité par la taille mémoire: chez moi, à partir de 10**8, j'ai "MemoryError". Pour monter plus haut, il faut utiliser un tableau binaire mais ça complique sérieusement le code. Avec celui-ci, on peut monter à 10 milliards (10**10)

Voilà mon code pour faire la même chose:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
def premiers(n):
    """Retourne la liste des nombres premiers inférieurs à n
       par la méthode du crible d'Eratosthene
    """
    tableau = [0, 0] + [x for x in range(2, n)]
    for i in range(2, int(n**0.5)):
        if tableau[i]!=0:
            tableau[i+i::i] = [0]*((n-i)//i-int((n-i)%i==0))
    return [nb for nb in tableau if nb!=0]

Avec ça, on trouve:
=> les 78498 nombres premiers inférieurs à 10**6 en 0.13s
=> les 664579 nombres premiers inférieurs à 10**7 en 1.40s

[marco056]

Oui, c'était juste pour comparer la liste des nombres premiers.

[wiztricks]

Salut,

Salut,

Voilà mon code pour faire la même chose:

Juste pour critiquer ce code:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
def premiers(n):
    """Retourne la liste des nombres premiers inférieurs à n
       par la méthode du crible d'Eratosthene
    """
    tableau = [0, 0] + [x for x in range(2, n)]
    for i in range(2, int(n**0.5)):
        if tableau[i]!=0:
            tableau[i+i::i] = [0]*((n-i)//i-int((n-i)%i==0))
    return [nb for nb in tableau if nb!=0]

Bon déjà, si on est préoccupé par la place mémoire, fabriquer une grande liste d'entiers différents, c'est occuper la place pour stocker tous ces entiers plus celles qui côté "liste" vont pointer dessus. Si on se contente de True, False on divise déjà çà par 2. De plus, on pourra écrire: [ False, False ] + [True,] * (n - 2) bien plus rapide que la compréhension de liste.
ligne 8, la construction [0]*((n-i)//i-int((n-i)%i==0)) est difficile à lire. De plus on fabrique une liste de zeros à chaque itération. On pourrait avoir une liste de False d'une longueur n//2 et en récupérer une tranche/slice.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
    zeros = [False,] * (n // 2)
    for i in range(2, int(n**0.5)):
        if tableau[i]!=0:
            q, r = divmod(n - i, i)
            tableau[2*i::i] = zeros[0 : q - (r == 0)]

On voit aussi qu'on va tester toutes les cases paires. On peut encore arranger çà avec:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
    zeros = [False,] * (n // 2)
    tableau[4::2] = zeros[2:n//2]
    for i in range(3, int(sqrt(n)), 2):
        if tableau[i]!=0:
            q, r = divmod(n - i, i)
            tableau[2*i::i] = zeros[0 : q - (r == 0)]

et on a réduit le temps de plus de 60% (sur ma machine).
Mais on peut exploser çà avec numpy:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
def premiers(n):
    array = np.ones(n, dtype=bool)
    zeros = np.zeros(n // 2, dtype=bool)
    array[0] = array[1] = False
    array[4::2] = zeros[2:n//2]
    for i in range(3, int(sqrt(n)), 2):
        if array[i]:
            q, r = divmod(n-i, i)
            array[2*i::i] = zeros[0:q - (r == 0)]
    return np.where(array==True)[0].tolist()

- W

[tyrtamos]

Bonjour wiztricks,

Juste pour critiquer ce code

Merci pour ces suggestions! En fait, j'ai déjà fait ça il y a quelques années avec un tableau logique, et c'est même sur mon site. Je ne l'ai pas mentionné parce que mon code était sous Python 2.x, et il a probablement beaucoup vieilli (dernière mise à jour en 2012). Je n'avais cependant pas utilisé toutes les astuces que tu signales, et je vais me les approprier .

Pour l'instant, je ne travaille pas avec numpy, mais j'essaierai un jour: merci pour le code!