Bonjour !

Je viens vous voir car en ce moment j'apprends le java et le python. J'ai codé en java un petit script qui permet de déterminer le nombre de nombres premiers sur un intervalle. Et pour l'entrainement j'ai voulu le traduire en python, j'ai pas eu trop de problèmes par contre je le trouve anormalement long... 18sec en python contre 0,2sec en Java...  Ca viendrais d'un manque d'optimisation de mon code? 

Python 

import time

nbMax = 0
nbFound = 0
resteDiv = 0

print("---------------------------------------")
print("       Calcul de nombres premiers      ")
print("---------------------------------------")
print("1- Calcul de l'intervale [1;x]")
print("2- Test d'un nombre spécifique")
print("---------------------------------------")

menuStr = input("Votre choix : ")
menu = int(menuStr)

if menu == 1:
    nbMaxStr = input("x = ? : ")
    nbMax = int(nbMaxStr)
    print("---------------------------------------")
    
    t = time.process_time()

    j = 1
    while j <= nbMax:
        
        nbDiviseurs = 0
        
        i = 1
        while i <= j:
            resteDiv = j % i
            
            if resteDiv == 0:
                nbDiviseurs += 1
            i+=1
                
        if nbDiviseurs == 2:
            print(j)
            nbFound += 1
                
        j+=2
        
    elapsed_time = time.process_time() - t

    print("---------------------------------------")
    print("Résultat = ",nbFound," nombres premiers sur l'intervale [1;",nbMax,"]")
    print("Temps d'éxecution =",elapsed_time,"secondes")
    print("---------------------------------------")

elif menu == 2:
    nbTestStr = input("Nombre à tester : ")
    nbTest = int(nbTestStr)
    print("---------------------------------------")

    nbDiviseurs = 0
    
    i = 1
    while i <= nbTest:
        resteDiv = nbTest % i
        
        if resteDiv == 0:
            nbDiviseurs += 1
        i+=1


    if nbDiviseurs == 2:
        print("Resultat =",nbTest,"est premier.")
    else:
        print("Resultat =",nbTest,"n'est pas premier.")


    print("---------------------------------------")

else:
    print("Choix invalide.")

Java

import java.util.Scanner;

public class NbPremiers {
    public static void main(String[] args){
        
    int NbMax;
    int NbFound = 0;
    long resteDiv;

    Scanner sc = new Scanner(System.in);
        
    System.out.println("---------------------------------------");
    System.out.println("       Calcul de nombres premiers      ");
    System.out.println("---------------------------------------");
    System.out.println("1- Calcul de l'intervale [1;x]");
    System.out.println("2- Test d'un nombre specifique");
    System.out.println("---------------------------------------");
    int menu = sc.nextInt();


	switch(menu) {
	case 1:
        System.out.println("x = ? :");
        sc.nextLine();
        NbMax = sc.nextInt();
        System.out.println("---------------------------------------");
            
        double start;
            
        start = System.currentTimeMillis();
            
	    for(int j=1; j <= NbMax ; j+=2){

		int nbDiviseurs = 0;
	
		for(int i=1; i <= j; i++)
		    {
			resteDiv = j % i;

			if(resteDiv == 0){

			    nbDiviseurs++;
		    
			}   
		    }

		if(nbDiviseurs == 2)
		{
			System.out.println(j);
			NbFound++;
		}
	    }
            
        double duree = (System.currentTimeMillis() - start) / 1000;
        
            
        System.out.println("---------------------------------------");
        System.out.println("Resultat = " + NbFound + " nombres premiers sur l'intervale [1;" + NbMax + "]");
        System.out.println("Temps d'execution = " + duree + " secondes");
        System.out.println("---------------------------------------");
	break;
            
	case 2:
        long nbTest;
            
        System.out.println("Nombre a tester = ? :");
        sc.nextLine();
        nbTest = sc.nextLong();
        System.out.println("---------------------------------------");
            
        int nbDiviseurs = 0;
            
        for(int i=1; i <= nbTest; i++)
        {
            resteDiv = nbTest % i;
                
            if(resteDiv == 0){
                    
            nbDiviseurs++;
                    
            }
        }
            
        if(nbDiviseurs == 2)
        {
            System.out.println("Resultat = " + nbTest + " est premier.");
        }
        else
        {
            System.out.println("Resultat = " + nbTest + " n'est pas premier.");
        }
            
        System.out.println("---------------------------------------");

	break;
            
    default:
	System.out.println("Aucun choix ne correspond.");
	break;
    }
        
    }

}

Salut, dans les deux cas, c'est excessivement long. Avant de chercher quoique ce soit, tu devrais déjà utiliser un crible d’Ératosthène. Avec ça, le calcul jusqu'à 10 000 est torché en 3 ms en Python et en un temps non mesurable en Fortran.

Ce qui prend du temps c'est l'affichage pour un algorithme équivalent, c'est tout !

oldProgrammer a écrit:

Ce qui prend du temps c'est l'affichage pour un algorithme équivalent, c'est tout !

LOL. C'est pas les 10000 prints qui vont jouer quoique ce soit comme rôle sur les 0.2 ou les 18 secondes. Le temps excessivement long provient simplement de l'algorithme utilisé.

EDIT : après test, 10000 print prennent environ 0.1-0.2 secondes en Python. Donc 1% des 18 secondes totales...

-
Edité par Anonyme 15 août 2014 à 23:35:00

LOL

On se croirait à la maternelle

C'est pas les 10000 prints qui vont jouer quoique ce soit comme rôle sur les 0.2 ou les 18 secondes. Le temps excessivement long provient simplement de l'algorithme utilisé.

Le PO s'en fou de l'algo, il fait un comparatif avec deux langages, et pour le même algorithme, ce qui prend le temps c'est l'affichage python qui est extrêmement lent. En utilisant une fonction et en retournant un générateur sur le même algorithme on gagne deux fois plus de temps.

Ce qui veut dire que l'affichage prend 50% et non 1%... du temps

EDIT: Il y a sans doute moyen de faire mieux en utilisant itertools et sa méthode count

-
Edité par Anonyme 16 août 2014 à 10:25:01

Utiliser un autre interpréteur que CPython pourrait peut-être accélérer les choses. Essaye de lancer ton code avec Pypy par exemple ?

oldProgrammer a écrit:

Le PO s'en fou de l'algo, il fait un comparatif avec deux langages, et pour le même algorithme, ce qui prend le temps c'est l'affichage python qui est extrêmement lent. En utilisant une fonction et en retournant un générateur sur le même algorithme on gagne deux fois plus de temps. Ce qui veut dire que l'affichage prend 50% et non 1%... du temps

Hem...

Avec ou sans affichage (me suis contenté de commenter la ligne print pour le second run, parce que si on change deux choses en même temps, on ne peut pas savoir ce qui a de l'influence... ), le temps est sensiblement le même. Par conséquent, et comme je l'ai déjà dit, l'affichage coute que dalle.

-
Edité par Anonyme 16 août 2014 à 10:53:44

J'ai simplement changé print par yield, et je gagne deux fois plus de temps, alors t'en conclu quoi ?

J'ai simplement changé print par yield, et je gagne deux fois plus de temps, alors t'en conclu quoi ?

Tu as écrit exactement :

En utilisant une fonction et en retournant un générateur sur le même algorithme on gagne deux fois plus de temps.

C'est la mise en fonction qui gagne du temps, pas le print qui en fait perdre.

-
Edité par Anonyme 16 août 2014 à 10:58:37

oldProgrammer a écrit:

J'ai simplement changé print par yield, et je gagne deux fois plus de temps, alors t'en conclu quoi ?

Pourrais-t-on voir ton code ?

Voilà le code modifié avec yield

import time

def calculate(maxi):
    global nbFound, resteDiv # pour pas tout modifier
    
    j = 1
    while j <= nbMax:
         
        nbDiviseurs = 0
         
        i = 1
        while i <= j:
            resteDiv = j % i
             
            if resteDiv == 0:
                nbDiviseurs += 1
            i+=1
                 
        if nbDiviseurs == 2:
            yield j # la modification print par yield
            nbFound += 1
                 
        j+=2


nbFound = 0
resteDiv = 0
 
print("---------------------------------------")
print("       Calcul de nombres premiers      ")
print("---------------------------------------")
print("1- Calcul de l'intervale [1;x]")
print("2- Test d'un nombre spécifique")
print("---------------------------------------")
 
menuStr = input("Votre choix : ")
menu = int(menuStr)
 
if menu == 1:
    nbMaxStr = input("x = ? : ")
    nbMax = int(nbMaxStr)
    print("---------------------------------------")
     
    t = time.process_time()
 
    for n in calculate(nbMax):
        print(n) # je retrouve bien mon print
         
    elapsed_time = time.process_time() - t
 
    print("---------------------------------------")
    print("Résultat = ",nbFound," nombres premiers sur l'intervale [1;",nbMax,"]")
    print("Temps d'éxecution =",elapsed_time,"secondes")
    print("---------------------------------------")
 
elif menu == 2:
    nbTestStr = input("Nombre à tester : ")
    nbTest = int(nbTestStr)
    print("---------------------------------------")
 
    nbDiviseurs = 0
     
    i = 1
    while i <= nbTest:
        resteDiv = nbTest % i
         
        if resteDiv == 0:
            nbDiviseurs += 1
        i+=1
 
 
    if nbDiviseurs == 2:
        print("Resultat =",nbTest,"est premier.")
    else:
        print("Resultat =",nbTest,"n'est pas premier.")
 
 
    print("---------------------------------------")
 
else:
    print("Choix invalide.")

Le résultat

Résultat =  1228  nombres premiers sur l'intervale [1; 10000 ]
Temps d'éxecution = 8.626007460999999 secondes

contre un peu plus de 14 secondes avec le code d'origine

Pourtant mon algo est identique, la seule différence c'est que je garde les résultats en mémoire pour les ressortir à la fin du calcul.

Si j'utilise les listes à la place de yield, j'ai 8 secondes aussi...

Effectivement après vérification, je me rend compte que le fait de mettre en fonction exactement le même code (avec print), le rend deux fois plus rapide, mais là je comprend pas, faut qu'on m'explique

Si j'utilise les boucles for on augmente l'efficacité à 6 secondes

J'ai quand même énormément de mal à comprendre comment avec ton premier code qui fait quand même un print tu arrivais à accuser ce dernier de bouffer du temps...

Enfin bref,

Effectivement après vérification, je me rend compte que le fait de mettre en fonction exactement le même code (avec print), le rend deux fois plus rapide, mais là je comprend pas, faut qu'on m'explique

Avec une petite recherche, on tombe là dessus.

Je vois pas en quoi un code si long est utile. Une simple fonction lambda suffit à trouver les nombres premiers:

premiers = lambda stop: [premier for premier in range(1, stop+1) if len([diviseur for diviseur in range(1, premier+1) if premier%diviseur == 0]) <= 2]

J'obtiens un temps avec premiers(10000) pas super bon mais le code est concis:

En affichant le retour:             7.948800086975098s
En n'affichant pas le retour:   5.929800033569336s

Edit: C'est illisible, certes. Voici une version (un peu) plus claire:

diviseurs = lambda x: [diviseur for diviseur in range(1, x+1) if x%diviseur == 0]

premiers = lambda stop: [premier for premier in range(1, stop+1) if len(diviseurs(premier)) <= 2]

-
Edité par Anonyme 18 août 2014 à 18:18:32

J'obtiens un temps pas super bon mais le code est concis:

Et illisible.

Bonjour à vous et je vois que y'a du débat haha ! Je commence à comprendre pourquoi y'a une dif entre les deux donc, mais je vais essayé également de suivre l'idée de @dri1 avec le crible pour l'entrainement et augmenté l'efficacité. 

D'ici quelques temps je reviendrais pour proposé mon code et le soumettre à vos remarques !

 - quelqun_dautre : Comment choisir l'interpréteur ?

Je l'exécute directement dans le terminal d'os X : 

python3 test.py

-
Edité par CactusTribe 16 août 2014 à 13:33:26

AlphaZeta a écrit:

Je vois pas en quoi un code si long est utile. Une simple fonction lambda suffit à trouver les nombres premiers:

Si ta fonction lambda contient plus d'une boucle ou bien dépasse les 80 caractères, ca ne devrait pas être une fonction lambda.

CactusTribe a écrit:

 - quelqun_dautre : Comment choisir l'interpréteur ?

Il faut installer Pypy (ici ?) et ensuite lancer ton programme avec "pypy test.py".

Je vois pas en quoi un code si long est utile. Une simple fonction lambda suffit à trouver les nombres premiers

Un code concis ne rend pas plus efficace un code

J'ai quand même énormément de mal à comprendre comment avec ton premier code qui fait quand même un print tu arrivais à accuser ce dernier de bouffer du temps..

 Imagines simplement que l'on passe de 10000 à 1000000, tu verras déjà une énorme différence, bien sûr il faut éviter ce type d'algorithme

Avec une petite recherche, on tombe là dessus.

 Merci, effectivement ça devient logique quand on y réfléchi

Imagines simplement que l'on passe de 10000 à 1000000, tu verras déjà une énorme différence, bien sûr il faut éviter ce type d'algorithme

Non mais d'un point de vue logique. Tu encapsules une partie du code dans une fonction, tu fais autant de print (mais juste pas au même moment), et comme ça va plus vite, tu en conclus que c'est le print qui prend du temps. C'est un peu comme si on changeait le moteur d'une voiture, qu'on intervertissait deux portières, et qu'ensuite comme on va plus vite, on en déduit que c'est le fait de changer les portières de place qui nous fait gagner en vitesse.

Par ailleurs, si on passe à un million, la responsabilité des print diminue en terme de proportion. Le code de l'OP fait N tests pour le nombre N. Donc pour aller jusque à N, on a une complexité en \(N\^3\) (en gros). C'est à dire qu'en multipliant par 100 la borne supérieure, tu multiplies en première approximation le temps d'exécution par un million. En revanche, le nombre de print est lui juste multiplié par 100. Par conséquent, tu perds proportionnellement de moins en moins de temps à faire des print qu'à tester la primalité des nombres lorsque tu augmentes la borne supérieure.

Si la question est « Est-ce que Python est plus lent que Jave ? »

• Oui, le typage dynamique impacte inévitablement sur le temps d'exécution. Mais c'est totalement négligeable avec le bon algorithme !

---

@dri1 t'a donné le nom de l'algorithme que tu dois utiliser « le crible d'Ératosthène ». En cherchant deux secondes, il est probable que tu tombes aussi sur le petit site de Tyrtamos. Je le cite parce que je trouve son implémentation du crible d'Ératosthène (dont l'idée de profiter de la puissance du slicing en Python) est magnifique.

def primes(n):
    if n < 2:
        return
    yield 2
    n += 1
    ls = [False, False] + [True] * (n - 2)
    ls[2::2] = [False] * ((n - 2) // 2 + n % 2)
    m = int(n**0.5)
    m += not m % 2
    for x in range(3, m + 1, 2):
        if ls[x]:
            yield x
            ls[x::x] = [False] * ((n - x) // x + ((n - x) % x > 0))
    for x in range(m, n, 2):
        if ls[x]:
            yield x

Comme la déjà fait remarquer quelqun_dautre, pour des perfs vaut mieux surtout utiliser pypy. Avec CPython j’obtiens 13 secondes alors qu’avec pypy j’obtient 0.7 seconde pour le code du PO. Quand au code de oldProgrammer, avec CPython j’obtiens 7.5 secondes contre 0.6 avec pypy.

Bon le code de psycopy prends un temps dérisoire bien entendu (CPython : 0.02, pypy : 0.06).

J’ai utilisé time.time() pour les mesures de temps, car je n’ai pas time.process_time() sur mon pypy.

Bonjour à vous !

J'ai bien téléchargé l'archive mac os X 32/64bits, mais je ne comprends pas comment l'installer pour que je puisse lancer mon script dans le terminal via : pypy test.py.

Comment je peut m'y prendre? pour le moment le terminal me dit "-bash : command not found"

Merci de votre aide 

oldProgrammer a écrit:

Ce qui veut dire que l'affichage prend 50% et non 1%... du temps

Tu dois être sous windows, où l'affichage console est d'une lenteur inqualifiable...

Lord Casque Noir a écrit:

oldProgrammer a écrit:

Ce qui veut dire que l'affichage prend 50% et non 1%... du temps

Tu dois être sous windows, où l'affichage console est d'une lenteur inqualifiable...

Ou pire, dans la console IDLE, où les print prennent 20 fois plus de temps (je viens de tester) que dans la console windows

@Lord, @tatrats,

Manqué ! Je suis sous Unix et j'utilise le gnome-terminal

EDIT: Mais les remarques sont bonnes, ça serait effectivement plus lent sous console Windows et IDLE

-
Edité par Anonyme 22 août 2014 à 9:47:59

Sur linux la vitesse dépend aussi pas mal du terminal (un joli avec des polices antialiasées sera plus lent)... mais bon, normalement on met pas de print dans un benchmark...

Bonjour ! 

Après des petites vacances je me remet à python :D 

Après vos remarques sur l'utilisation du crible j'ai trouvé ce sujet : http://fr.openclassrooms.com/forum/sujet/crible-d-eratosthene-87347

En essayant étapes après étapes j'ai effectivement vu des grosses différences de temps d'exécutions, je n'ai pas codé mon propre crible car j'ai encore du mal à bien saisir toutes les étapes. 

Mon but étant de pouvoir finir le problème 3 sur EulerProject, il faut que je puisse atteindre 600 851 475 143.

J'ai donc d'abord utilisé ce crible (j'ai juste arrangé l'affichage à ma sauce) : 

Erat.py 

import time

def primes(lim):
    # cas particuliers
    if lim<5:
        if lim<2: return
        yield 2
        if lim<3: return
        yield 3
        return
    
    n = (lim-1)//6
    primeM=[True]*(n+1) # p=2*i-1
    primeP=[True]*(n+1) # p=2*i+1
    primeM[0]=False # 2*0-1 pas premier
    primeP[0]=False # 2*0+1 pas premier
    for i in range((int(lim**0.5)+1)//6+1):
        if primeM[i]: # 6*i-1 est premier
            p = 6*i-1
            primeM[p+i::p]=[False]*((n-i)//p)
            primeP[p-i::p]=[False]*((n+i)//p)
        if primeP[i]: # 6*i+1 est premier
            p = 6*i+1
            primeM[p+i::p]=[False]*((n-i)//p)
            primeP[p-i::p]=[False]*((n+i)//p)
    
    yield 2
    yield 3
    for i in range(n): # un rang avant la fin en n
        if primeM[i]: yield 6*i-1
        if primeP[i]: yield 6*i+1
    # pour mieux gérer la fin
    if primeM[n] and 6*n-1<=lim: yield 6*n-1
    if primeP[n] and 6*n+1<=lim: yield 6*n+1
    return


limit = 10**4
st=time.time()

listePremiers = list(primes(limit))

execTime = time.time()-st

print("--------------------------------------------------------")
print("Interval = [ 1 -", limit, "]")
print("Highest prime number = ", listePremiers[-1])
print("Sum of all primes numbers = ", sum(listePremiers))
print("Execute time = ",execTime, "seconds")
print("--------------------------------------------------------")

Ensuite ne pouvant dépasser 10^(8) à cause d'un out of memory j'ai essayé avec le crible suivant : 

Erat3.py

import time

def primes(lim):
    # cas particuliers
    if lim<7:
        if lim<2: return
        yield 2
        if lim<3: return
        yield 3
        if lim<5: return
        yield 5
        return
    
    n = (lim-1)//30
    prime1 = [True]*(n+1)
    prime7 = [True]*(n+1)
    prime11 = [True]*(n+1)
    prime13 = [True]*(n+1)
    prime17 = [True]*(n+1)
    prime19 = [True]*(n+1)
    prime23 = [True]*(n+1)
    prime29 = [True]*(n+1)
    prime1[0] = False
    i = l = 0
    while l<=n:
        if prime1[i]:
            p = 30*i+1
            l = i*(p+1)
            prime1[l::p] = [False]*(1+(n-l)//p)
            l += i*6
            prime7[l::p] = [False]*(1+(n-l)//p)
            l += i*4
            prime11[l::p] = [False]*(1+(n-l)//p)
            l += i*2
            prime13[l::p] = [False]*(1+(n-l)//p)
            l += i*4
            prime17[l::p] = [False]*(1+(n-l)//p)
            l += i*2
            prime19[l::p] = [False]*(1+(n-l)//p)
            l += i*4
            prime23[l::p] = [False]*(1+(n-l)//p)
            l += i*6
            prime29[l::p] = [False]*(1+(n-l)//p)
        if prime7[i]:
            p = 30*i+7
            l = i*(p+7)+1
            prime19[l::p] = [False]*(1+(n-l)//p)
            l += i*4+1
            prime17[l::p] = [False]*(1+(n-l)//p)
            l += i*2+1
            prime1[l::p] = [False]*(1+(n-l)//p)
            l += i*4
            prime29[l::p] = [False]*(1+(n-l)//p)
            l += i*2+1
            prime13[l::p] = [False]*(1+(n-l)//p)
            l += i*4+1
            prime11[l::p] = [False]*(1+(n-l)//p)
            l += i*6+1
            prime23[l::p] = [False]*(1+(n-l)//p)
            l += i*2+1
            prime7[l::p] = [False]*(1+(n-l)//p)
        if prime11[i]:
            p = 30*i+11
            l = i*(p+11)+4
            prime1[l::p] = [False]*(1+(n-l)//p)
            l += i*2
            prime23[l::p] = [False]*(1+(n-l)//p)
            l += i*4+2
            prime7[l::p] = [False]*(1+(n-l)//p)
            l += i*2
            prime29[l::p] = [False]*(1+(n-l)//p)
            l += i*4+2
            prime13[l::p] = [False]*(1+(n-l)//p)
            l += i*6+2
            prime19[l::p] = [False]*(1+(n-l)//p)
            l += i*2+1
            prime11[l::p] = [False]*(1+(n-l)//p)
            l += i*6+2
            prime17[l::p] = [False]*(1+(n-l)//p)
        if prime13[i]:
            p = 30*i+13
            l = i*(p+13)+5
            prime19[l::p] = [False]*(1+(n-l)//p)
            l += i*4+2
            prime11[l::p] = [False]*(1+(n-l)//p)
            l += i*2+1
            prime7[l::p] = [False]*(1+(n-l)//p)
            l += i*4+1
            prime29[l::p] = [False]*(1+(n-l)//p)
            l += i*6+3
            prime17[l::p] = [False]*(1+(n-l)//p)
            l += i*2+1
            prime13[l::p] = [False]*(1+(n-l)//p)
            l += i*6+3
            prime1[l::p] = [False]*(1+(n-l)//p)
            l += i*4+1
            prime23[l::p] = [False]*(1+(n-l)//p)
        if prime17[i]:
            p = 30*i+17
            l = i*(p+17)+9
            prime19[l::p] = [False]*(1+(n-l)//p)
            l += i*2+1
            prime23[l::p] = [False]*(1+(n-l)//p)
            l += i*4+3
            prime1[l::p] = [False]*(1+(n-l)//p)
            l += i*6+3
            prime13[l::p] = [False]*(1+(n-l)//p)
            l += i*2+1
            prime17[l::p] = [False]*(1+(n-l)//p)
            l += i*6+3
            prime29[l::p] = [False]*(1+(n-l)//p)
            l += i*4+3
            prime7[l::p] = [False]*(1+(n-l)//p)
            l += i*2+1
            prime11[l::p] = [False]*(1+(n-l)//p)
        if prime19[i]:
            p = 30*i+19
            l = i*(p+19)+12
            prime1[l::p] = [False]*(1+(n-l)//p)
            l += i*4+2
            prime17[l::p] = [False]*(1+(n-l)//p)
            l += i*6+4
            prime11[l::p] = [False]*(1+(n-l)//p)
            l += i*2+1
            prime19[l::p] = [False]*(1+(n-l)//p)
            l += i*6+4
            prime13[l::p] = [False]*(1+(n-l)//p)
            l += i*4+2
            prime29[l::p] = [False]*(1+(n-l)//p)
            l += i*2+2
            prime7[l::p] = [False]*(1+(n-l)//p)
            l += i*4+2
            prime23[l::p] = [False]*(1+(n-l)//p)
        if prime23[i]:
            p = 30*i+23
            l = i*(p+23)+17
            prime19[l::p] = [False]*(1+(n-l)//p)
            l += i*6+5
            prime7[l::p] = [False]*(1+(n-l)//p)
            l += i*2+1
            prime23[l::p] = [False]*(1+(n-l)//p)
            l += i*6+5
            prime11[l::p] = [False]*(1+(n-l)//p)
            l += i*4+3
            prime13[l::p] = [False]*(1+(n-l)//p)
            l += i*2+1
            prime29[l::p] = [False]*(1+(n-l)//p)
            l += i*4+4
            prime1[l::p] = [False]*(1+(n-l)//p)
            l += i*2+1
            prime17[l::p] = [False]*(1+(n-l)//p)
        if prime29[i]:
            p = 30*i+29
            l = i*(p+29)+28
            prime1[l::p] = [False]*(1+(n-l)//p)
            l += i*2+1
            prime29[l::p] = [False]*(1+(n-l)//p)
            l += i*6+6
            prime23[l::p] = [False]*(1+(n-l)//p)
            l += i*4+4
            prime19[l::p] = [False]*(1+(n-l)//p)
            l += i*2+2
            prime17[l::p] = [False]*(1+(n-l)//p)
            l += i*4+4
            prime13[l::p] = [False]*(1+(n-l)//p)
            l += i*2+2
            prime11[l::p] = [False]*(1+(n-l)//p)
            l += i*4+4
            prime7[l::p] = [False]*(1+(n-l)//p)
        i+=1
    yield 2
    yield 3
    yield 5
    for i in range(n):
        if prime1[i]: yield 30*i+1
        if prime7[i]: yield 30*i+7
        if prime11[i]: yield 30*i+11
        if prime13[i]: yield 30*i+13
        if prime17[i]: yield 30*i+17
        if prime19[i]: yield 30*i+19
        if prime23[i]: yield 30*i+23
        if prime29[i]: yield 30*i+29
    if prime1[n] and (30*n+1)<=lim: yield 30*n+1
    if prime7[n] and (30*n+7)<=lim: yield 30*n+7
    if prime11[n] and (30*n+11)<=lim: yield 30*n+11
    if prime13[n] and (30*n+13)<=lim: yield 30*n+13
    if prime17[n] and (30*n+17)<=lim: yield 30*n+17
    if prime19[n] and (30*n+19)<=lim: yield 30*n+19
    if prime23[n] and (30*n+23)<=lim: yield 30*n+23
    if prime29[n] and (30*n+29)<=lim: yield 30*n+29


limit = 10**4
st=time.time()

listePremiers = list(primes(limit))

execTime = time.time()-st

print("--------------------------------------------------------")
print("Interval = [ 1 -", limit, "]")
print("Highest prime number = ", listePremiers[-1])
print("Sum of all primes numbers = ", sum(listePremiers))
print("Execute time = ",execTime, "seconds")
print("--------------------------------------------------------")

Les performances sont meilleures mais il y a un soucis, ce dernier crible oubli 9997 

J'ai fais plusieurs essais sans trouver la véritable cause à cet oubli...

Je m'en remet donc à vous car je ne peut pas aller plus loin si le résultat n'est pas correcte x) 

Je vous remercie !

EDIT : Je passe maintenant par Pypy3 suites aux remarques sur les performances !

-
Edité par CactusTribe 28 août 2014 à 16:28:06

Salut,

Tes cribles sont faux : 9991 (97*103) et 9997 (13*769) ne sont pas premiers, 9973 l'est.

-
Edité par LOLivier 28 août 2014 à 17:29:12

Merci ! effectivement il y avais quelques petits soucis maintenant c'est impec et je trouve bien 9973 comme dernier nombre premier

Ce n'est pas du crible dont tu as besoin pour ce problème (et heureusement d'ailleurs, puisque faire un crible jusqu'à des nombres aussi grand nécessiterai une mémoire délirante).