Discussion :

[pijaku]

mais je ne fait que suivre l'idée de unparia avec son tableau

Non, pas tout à fait.
L'idée d'unparia est :

tu pars du chiffre 2 et mets à True tous ses multiples, jusqu'à 52 (ses multiples correspondront très exactement à leur index dans le tableau)
- tu passes au suivant et refais la même chose avec ses multiples

Cela implique forcément (à moins que je ne me trompe) une double boucle :

Code :

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

1
2
For i = 2 To machin
   For j = truc To bidule Step mouche

Après l'optimisation du code consiste à :
> trouver les meilleurs "machin", "truc", "bidule" et "mouche",
> trouver les bons tests à réaliser ET les ordonner dans cette double boucle (en évitant soigneusement AND),
> utiliser à bon escient les outils de VBA (donc éviter Mod trop gourmant, éviter un ReDim Preserve à chaque tour de boucle, etc...)

C'est ce que j'ai trouvé d'intéressant dans cette discussion car, contrairement à vous tous, j'ai tendance à ne jamais optimiser mes codes.
Considérant qu'avec Excel on ne dépasse jamais vraiment les limites raisonnables.

[patricktoulon]

oui mais effectivement ca suppose une double boucle imbriqué

tu pars du chiffre 2 et mets à True tous ses multiples, jusqu'à 52 (ses multiples correspondront très exactement à leur index dans le tableau)
- tu passes au suivant et refais la même chose avec ses multiples

ce qui fait pas mal de boucle et ca m'étonnerait a ce titre que modulo soit plus gourmand

et si modulo est trop gourmand on peut se servir de ma 2d versions avec la comparaison de fix(nombre) au nombre que j'ai proposé plus haut
ce qui fait exactement la même chose que mod en interprétation différente (interprétation de mod /résultat negatif ou pas sur le "=")

j'essaie le truc de marc mais je ne trouve pas la bonne formule pour retomber sur mes pattes

et oui c'est quand même important d'optimiser

en tout cas toutes les méthodes qui ont été proposée me mette toutes 99 comme nombre premiers c'est balo!!!

[pijaku]

j'essaie le truc de marc mais je ne trouve pas la bonne formule pour retomber sur mes pattes

C'est exactement ce que je te disais dans mon message précédent, à savoir trouver les meilleurs "machin", "truc", "bidule" et "mouche" dans :

Code :

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

1
2
For i = 2 To machin
   For j = truc To bidule Step mouche

Allez, je t'aide un peu...
Eriiic (salut l'ami) nous a déjà indiqué (voir son message plus haut) qu'elle est la meilleure valeur pour "machin".
Il ne s'agit pas du tiers de n...
Cela implique forcément la valeur de "truc" (là c'est purement mathématique).
"bidule" doit représenter le maximum, et "mouche", je te laisse le chercher un peu.

EDIT :
J'oubliais...
Tous les tests réalisés ici prouvent que Modulo est plus lent (s'il n'est pas plus gourmand) qu'une double boucle.

[patricktoulon]

re ca y est je pense avoir optimisé avec n/3

purée mal réveillé ce matin moi
voila avec modulo et n/3 n etant le nombre demandé /3 j'ai mémé essayé 6 ca match aussi
on reduit le nombre d'itération dans la boucle for

Code :

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

1
2
3
4
5
6
7
Function Est_un_nombre_Premier(nombre As Long) As Boolean
Dim div As Long
For div = 2 To nombre / IIf(nombre > 3, nombre / 3, nombre)
If nombre Mod div = 0 Then Est_un_nombre_Premier = False: Exit Function ' permet aussi de sortir a false si c'est le cas (gain de temps )
Next
Est_un_nombre_Premier = True
End Function

Code :

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

1
2
3
4
5
6
7
8
9
10
11
Sub test()
Dim i As Long, T
T = Timer
oldnombre = 1
For i = 1 To 1500
If Est_un_nombre_Premier(i) Then N = N & " " & i
Next
T = Timer - T
Debug.Print N
Debug.Print "calculé en " & T & " secondes"
End Sub

je ne sais pas si c'est ca qu'expliquait MarcL

[pijaku]

je ne sais pas si c'est ca qu'expliquait MarcL

Non, je ne pense pas.
Relis mon message précédent (13h30).

Pour ton info, avec cette méthode de double boucle, on arrive à trouver les 664 578 nombres premiers compris entre 2 et 10 000 000 en moins de 4,5 secondes.
Ce que tu ne parviendras jamais à réaliser avec Mod et/ou Fix.

[Marc-L]

Salut ! Il y a du monde !

@Marc-L : Qu'est ce que tu appelles Modulo2 ?

En fait c'est juste le nom d'une procédure, une variante de la première …

A la racine carrée non ?

pour la racine carrée

Pour ne pas mettre l'étudiant sur la voie car non seulement il a un support de cours
mais aussi ce n'est pas compliqué d'effectuer une recherche sur le Net
donc j'en étais resté à la pure logique arithmétique niveau collège mais pour Patrick
je confirme le plus efficace est bien de se limiter à la racine carrée de n comme démontré par Erathostène …


Ceci dit, j'ai optimisé mes procédures, l'ancienne Modulo1 (au tiers de n) est devenue la Modulo2
et la nouvelle Modulo1 a été portée au niveau du crible et elle lui tient la dragée haute ! (en fait non, voir l'Edit en bas …)

Tests i5 2.5GHz, juste le temps de calculs sans tenir compte de l'affichage dans la feuille :

Pour 11 000 :

Modulo1 : 0,000s
Crible     : 0,016s
Modulo2 : 0,063s

A noter à 10 000 le crible est à zéro sauf si je le teste en premier il décroche avant dans les 9 500+ …

Pour 21 500 :

Modulo1 : 0,000s
Crible     : 0,016s
Modulo2 : 0,141s

Pour 22 000 :

Modulo1 : 0,016s
Crible     : 0,031s
Modulo2 : 0,141s

Pour 50 000 :

Modulo1 : 0,031s
Crible     : 0,063s
Modulo2 : 0,641s …

Edit : tout dépend où l'on décide d'arrêter le chronomètre …

Pour le crible après la dernière boucle je supprime les non premiers de la variable tableau via la fonction VBA Filter.
Les temps ci-dessus sont arrêtés juste après cette fonction.
Si par contre le temps est décompté avant cette fonction juste après la sortie de la boucle, le crible repasse devant Modulo1.
Et je n'utilise pas la fonction Filter pour le modulo …

[patricktoulon]

perso avec 9 dans mon "iif" j'ai zero pour 20000
et si je formate pas le timer j'ai

[pijaku]

Merci Marc-L pour ces explications.

Je serais assez curieux de voir ta Sub "crible" (en MP si tu veux bien) car avec la mienne j'obtiens de bien meilleurs temps.
Pour 100 000 : 0,03125 seconde
Matériel : 1,80 GHz de processeur

[patricktoulon]

re
dans cet exercice c'est pas le processeur qui compte vraiment ce sont tes mémoires et la vitesse de leur Bus
avec un 3 giga et les même mémoire que toi je ferait pareille
moi aussi j'aimerais bien voir son code a MarcL


après je viens de me rendre compte que je travail sur un string ce qui est normalement plus lourd qu'un tableau
a prendre en considération

re
je viens d'essayer ma méthode avec une variable tableau je réduit le temps par 2.5 pour 20000 je fait le même temps que 7500 en string soit 0,015625 autrement dit T formaté j'ai zero

[Marc-L]

J'ai édité mon message précédent quant au chronométrage …

1.80GHz certes mais avec quel processeur ? Si tu as un i7 avec un Excel récent, moi c'est un i5 + xl2003 …
Sinon je me suis peut-être fourvoyé pour le crible …

Pour 100 000 :

Crible     : 0,047s   (avant Filter)
Modulo1 : 0,094s
Crible     : 0,141s   (après Filter)
Modulo2 : 2,215s …

Patrick, je confirme pour le string j'avais essayé pour ma première version de Modulo2 avec une Collection …

[joe.levrai]

le nombre premier ne sont divisible que par 1 ou lui même ce sont donc forcement des impairs
sachant ca je vois vraiment pas pourquoi on irais chercher "sqr" et tout le reste

Le but n'est pas de démontrer pourquoi on peut rationnaliser l'algorithme en s'arrêtant à la racine carrée du nombre à tester(*).
En revanche, il permet de drastiquement réduire les nombres à manipuler.

Sur un algorithme de factorisation d'un nombre en ses nombres premiers, crois-moi, si tu oublies d'y ajouter la limite sur la racine carrée, tu vas très vite aboutir à un algo non linéaire et même risquer le polynomial (voir l'exponentiel).



(*) aller une piste : le carré d'un nombre = nombre*nombre ... donc le carré d'un nombre n'est pas premier et possède un autre divisieur que 1 et lui-même ==> sa racine carrée.

[pijaku]

Pour ma "config" : Intel® Celeron® Processor G460 (1.5M Cache, 1.80 GHz)
Windows 7 + Excel 2010.

Quant aux temps de calcul, pour ma Sub, c'est après restitution des résultats dans une variable tableau bien dimensionnée.
Je te l'envoie, si tu veux, par messagerie privée pour que tu compares résultats et temps de calculs.

[patricktoulon]

re
je viens de faire divers test avec modulo sqt redim preserve
et selon le mode choisi ca diffère
avec sqr pour la limite ca rallonge chez moi

je suis sur l'AMD 3.6G mémoire 24 g dispo vitesse 1668 sur 32 j'en aurait simplement 4 cela serait pareil c'est une question de bus

d'ailleur sur le PC portable hp pavillon proc 2.5 g et 4 g mémoire vitesse de bus 800 j'ai exactement le même résultat

test effectué

Code :

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

1
2
3
4
5
6
7
8
Function Est_un_nombre_Premier(nombre As Long) As Boolean
Dim div As Long
'For div = 2 To Round(Sqr(nombre)) ' calculé en 0,046875 secondes pour 20000
For div = 2 To nombre / IIf(nombre > 9, nombre / 9, nombre) 'calculé en 0,015625 secondes pour 20000
If nombre Mod div = 0 Then Est_un_nombre_Premier = False: Exit Function ' permet aussi de sortir a false si c'est le cas (gain de temps )
Next
Est_un_nombre_Premier = True
End Function

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
 
Sub test()
Dim i As Long, T
T = Timer
nombre = 20000
ReDim tablo(nombre) As Variant
a = 0
For i = 1 To nombre
If Est_un_nombre_Premier(i) Then tablo(a) = i: a = a + 1
Next
T = Timer - T
'==========================================================================================================
' si je preserve uniquement les item du tableau rempli je remonte a 0.0325
'ReDim Preserve tablo(0 To a)
'Debug.Print Join(tablo, " ")
'===========================================================================================================
' si je trim simplement le join du tablo sans enlever les item vides je redescend a 0,015625
Debug.Print Trim(Join(tablo, " "))
Debug.Print "calculé en " & T & " secondes"
End Sub

débloquez ou débloquez les ligne selon le test dans fonction et sub test

[Marc-L]

Ok pour ton code en MP pour tester !

C'est l'utilisation de la fonction Filter qui grève déjà pas mal le crible à la fin comme le montre mon précédent post …

Patrick, je t'enverrais le code de Pikaju & les miens …

[pijaku]

@Marc-L :
J'ai essayé de t'envoyer un MP, mais je n'ai rien dans mes éléments envoyés.
J'ai du me gourer dans la manœuvre.
Pourrais tu m'envoyer un message privé que je puisses y répondre?

[Marc-L]

Merci Pijaku, j'ai bien reçu ton message !

Résultat de ton code (purée c'est tellement simple ! Je suis resté dans du procédural de collégien,
j'aurais dû regarder Wikipedia bien plus tôt en attendant l'algorithme de l'étudiant … ) :

pour 8 000 000 :   0,996s   539776 nombres premiers de 2 à 7999993

pour    100 000 :   0,016s   9591 nombres premiers de 2 à 99991 …


J'ai utilisé qu'une seule variable tableau alors qu'avec deux c'est tellement plus efficace !

Bref unparia n'a rien loupé, il a bien fait d'aller à la pêche !

[patricktoulon]

re
je veux bien le code de pikaju moi aussi

[pijaku]

Hej !
Comme quoi il n'y a pas que des bêtises sur Wikipédia!

Par contre, je suis jaloux. Ton pc est plus rapide que le mien

1,695313 539776 nombres premiers, de 2 à 7999993

Pfff

[Marc-L]

C'est normal vu la différence de processeur et de fréquence !

Ton code pour 100 000 a affiché une fois 0,000s, peut-être le cache …

Patrick t'a dû recevoir le code de Pijaku !

[patricktoulon]

re
je viens de tester pour 20000 le code pikaju et j'ai le 2d temps que j'ai avec mon modulo et sqr sur redim tablo soit temps ecoulé0,03125secondes

par contre j'ai été obligé d'alimenter une variable string le debug.print join(liste," ") me déclenche une erreur va savoir

désolé chez moi modulo plus rapide pour le même MAX

ca n'est que la suggestion de unparia en fait

EDIT:
re ca y est j'ai compris en l'etat a la fin la liste est inexploitable
il faut rebouclé pour en récupérer les index
parti de la je vois difficilement votre vision du "optimiser"
sachant que c'est plus long et en plus il faut reboucler car les élément a false sont inexploitables avec join par exemple
d'ailleurs faite le test

Code :

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

1
2
3
4
Sub test3()
Dim tablo(20) As Boolean
Debug.Print Join(tablo, " ")
End Sub