Liste des nombres premiers (methode eratosthenes)

[Zorro]

Code : Tout sélectionner

;***********************************************
;Titre  :*nombre_premier (methode eratosthene)
;Auteur  : Zorro
;Date  :06/10/2016
;Heure  :22:54:16
;Version Purebasic :  PureBasic 5.50 (Windows - x86)
;Version de l'editeur :EPB V2.64
; Libairies necessaire : Aucune 
;***********************************************
;{- Enumerations / DataSections
;{ Windows
Enumeration
		#Win
EndEnumeration
;}
;{ Gadgets
Enumeration
		#Editor
		#Button_go
		#Button_stop
		#String_depart
		#String_arrive
		#progress_bar
		#chrono
EndEnumeration
;}
Global start.q,arrive.q,Flag,Flag2,N.q


Global Sortie.s
Global mem_np=2
Global Addition=2
Declare openwindow_win()
Declare boss1(bidon)
Declare boss2(bidon)
Declare boss3(bidon)
Declare boss4(bidon)
Declare.s eratosthenes(start,n)
Declare paire_impaire(nombre)

Define.l Event
;}
OpenWindow_Win()
;{- Event loop
Repeat
		Event = WaitWindowEvent(12)
		Select Event
				; ///////////////////
		Case #PB_Event_Gadget
				Select EventGadget()
				Case #Editor
				Case #Button_go
						start.q=val(GetGadgetText(#String_depart))
						N.q=val(GetGadgetText(#String_arrive))
						if paire_impaire(start.q) =#true
								start.q=start.q+1
						Endif
						ClearGadgetItems(#editor)
						SetGadgetAttribute(#progress_bar, #PB_ProgressBar_Maximum, N)
						TempsDepart.f = ElapsedMilliseconds() 
						;calldebugger
						eratosthenes(start,N)	
						
						TempsEcoule.f = (ElapsedMilliseconds()-TempsDepart.f  )/1000 ; en secondes
						SetGadgetText(#chrono,"Temp:"+strF( TempsEcoule.f,3 )+" secondes")						
						SetGadgetText(#editor, Sortie.s)
				Case #String_depart
						start=val(GetGadgetText(#String_depart))
				Case #String_arrive
						arrive=val(GetGadgetText(#String_arrive))
				EndSelect
				; ////////////////////////
		Case #PB_Event_CloseWindow
				Select EventWindow()
				Case #Win
						CloseWindow(#Win)
						Break
				EndSelect
		EndSelect
Forever
;
;}
; procedure zone
Procedure OpenWindow_Win()
		If OpenWindow(#Win, 457, 159, 400, 400, "nombre premier", #PB_Window_SystemMenu|#PB_Window_SizeGadget|#PB_Window_MinimizeGadget|#PB_Window_TitleBar)
				EditorGadget(#Editor, 20, 75, 355, 300)
				ButtonGadget(#Button_go, 20, 5, 85, 30, "GO")
				ButtonGadget(#Button_stop, 130, 5, 85, 30, "Stop")
				StringGadget(#String_depart, 230, 10, 130, 20, "1", #PB_String_Numeric)
				StringGadget(#String_arrive, 230, 40, 130, 20, "80000000", #PB_String_Numeric)
				ProgressBarGadget(#progress_bar, 20,385, 355, 10, 0, 100)
				TextGadget(#chrono,20,40,200,15,"Temp:"+"0.00")
		EndIf
EndProcedure


Procedure.s eratosthenes(start,N)
		Dim N(N+10); 
		Sortie.s=""
		if Start<2 
				Sortie.s=Sortie.s+"2"+" "+chr(10)
		Endif
		For X = start To N Step 2           
				Divis = 0
				For Y = 2 To Sqr(X)
						If mod(X , Y )= 0 								
								Divis + 1
						EndIf
				Next  Y
				If Divis = 0 	and x<>1			
						Sortie.s=Sortie.s+Str(X)+" "+chr(10)
				EndIf
				Event =WaitWindowEvent(2)
				if event=#PB_Event_Gadget
						Select EventGadget()
						Case #Button_stop
								SetGadgetText(#editor, Sortie.s)
								ProcedureReturn Sortie.s
						Endselect
				Endif
				SetGadgetState(#progress_bar, x)
		Next  X 
		
		ProcedureReturn Sortie.s
EndProcedure
Procedure paire_impaire(nombre)
		If nombre % 2 <> 0  ; nombre impaire
				retour = #false
		Else ; nombre paire
				retour= #True ; paire
		EndIf
		ProcedureReturn retour
EndProcedure
;Epb

[Zorro]

methode bourrin on regarde tout
et on regarde si c'est divisible par autre chose que lui-meme et 1
c'est plus lent que le code ci dessus

Code : Tout sélectionner

;***********************************************
;Titre  :*nombre_premier (methode bourrin )
;Auteur  : Zorro
;Date  :06/10/2016
;Heure  :22:54:16
;Version Purebasic :  PureBasic 5.50 (Windows - x86)
;Version de l'editeur :EPB V2.64
; Libairies necessaire : Aucune
;***********************************************

;{- Enumerations / DataSections
;{ Windows
Enumeration
		#Win
EndEnumeration
;}
;{ Gadgets
Enumeration
		#Editor
		#Button_go
		#Button_stop
		#String_depart
		#String_arrive
		#progress_bar
		#chrono
EndEnumeration
;}
Global start.q,arrive.q,Flag,Flag2
Declare openwindow_win()
Declare paire_impaire(nombre)
Define.l Event
;}

OpenWindow_Win()
;{- Event loop
Repeat
		Event = WaitWindowEvent(12)
		Select Event
				; ///////////////////
		Case #PB_Event_Gadget
				Select EventGadget()
				Case #Editor
				Case #Button_go
						
						ClearGadgetItems(#editor)
						sortie.s="" 
						SetGadgetState(#progress_bar, 1)
						
						start.q=val(GetGadgetText(#String_depart))
						if paire_impaire(start.q) =#true
						start.q=start.q+1
						Endif
						arrive.q=val(GetGadgetText(#String_arrive))
						TempsDepart.f = ElapsedMilliseconds() 
						N.q=arrive.q-start.q
						SetGadgetAttribute(#progress_bar, #PB_ProgressBar_Maximum, N)
						if Start.q=1
								sortie.s= sortie.s+"2"+chr(10)
						Endif
						For x=start to arrive step 2   
								For y= 2 to x-1                        
										r.f=x/y
										test.f=r.f-int(r.f)
										if test.f>0
												test2.s=ReverseString(str(x))
												if len(test2.s)>1
														if left(test2.s,1)="0" or left(test2.s,1)="2" or left(test2.s,1)="4" or left(test2.s,1)="6" or left(test2.s,1)="8" or left(test2.s,1)="5"
																Flag=#false
																break
														Endif
												endif
												Flag=#True
										Else
												Flag=#false
												break
										Endif
								Next y
								if flag=#True                                 
										sortie.s=sortie.s+str(x)+chr(13)                          
										Event =WaitWindowEvent(2)
										if event=#PB_Event_Gadget
												Select EventGadget()
												Case #Button_stop
														start=1
														arrive=1
												Endselect
										Endif
								Endif
								SetGadgetState(#progress_bar, x)
						Next x
						TempsEcoule.f = (ElapsedMilliseconds()-TempsDepart.f  )/1000 ; en secondes
						SetGadgetText(#chrono,"Temp:"+strF( TempsEcoule.f,3 )+" secondes")				
						SetGadgetText(#editor, Sortie.s)
				Case #String_depart
						start=val(GetGadgetText(#String_depart))
				Case #String_arrive
						arrive=val(GetGadgetText(#String_arrive))
				EndSelect
				; ////////////////////////
		Case #PB_Event_CloseWindow
				Select EventWindow()
				Case #Win
						CloseWindow(#Win)
						Break
				EndSelect
		EndSelect
Forever
;
;}
; procedure zone
Procedure OpenWindow_Win()
		If OpenWindow(#Win, 457, 159, 400, 400, "nombre premier", #PB_Window_SystemMenu|#PB_Window_SizeGadget|#PB_Window_MinimizeGadget|#PB_Window_TitleBar)
				EditorGadget(#Editor, 20, 75, 355, 300)
				ButtonGadget(#Button_go, 20, 5, 85, 30, "GO")
				ButtonGadget(#Button_stop, 130, 5, 85, 30, "Stop")
				StringGadget(#String_depart, 230, 10, 130, 20, "1", #PB_String_Numeric)
				StringGadget(#String_arrive, 230, 40, 130, 20, "80000000", #PB_String_Numeric)
				ProgressBarGadget(#progress_bar, 20,385, 355, 10, 0, 100)
				TextGadget(#chrono,20,40,200,15,"Temp:"+"0.00")
		EndIf
EndProcedure
Procedure paire_impaire(nombre)
  If nombre % 2 <> 0  ; nombre impaire
    retour = #false
    
  Else ; nombre paire
    retour= #True ; paire
  EndIf
  ProcedureReturn retour
EndProcedure


; Epb

[Zorro]

modification des deux codes ci dessus, pour y ajouter un progressbarr

on gagne en vitesse a ne pas afficher chaque sortie

ps: je precise que dans le 1er code le champ de depart est toujours a 1

[Micoute]

Tu as tord, puisque 1 n'est pas un nombre premier, moi j'afficherais 2 et 3 et je commencerais à 5 puisque 4 est divisible par 2 et je compterais avec un pas pair.

[Zorro]

Tu as tord, puisque 1 n'est pas un nombre premier, moi j'afficherais 2 et 3 et je commencerais à 5 puisque 4 est divisible par 2 et je compterais avec un pas pair.

il semble que tu n'es pas essayé mon code !

essaye le, et reviens j'attends la suite

[Micoute]

Ne t'offusque pas, c'était juste pour plaisanter.

Re edit
J'ai oublier d'annoncer qu'il très rapide, qu'on peut démarrer depuis n'importe quel nombre jusqu'à n'importe quel autre nombre.

[Zorro]

J'ai oublier d'annoncer qu'il très rapide, qu'on peut démarrer depuis n'importe quel nombre jusqu'à n'importe quel autre nombre.

le deuxieme code seulement ...
le premier, il faudrai que je fasse la modif ..

[Zorro]

voila , maintenant tout les codes marchent avec le parametre debut et fin

j'ai aussi ajouté un chrono histoire de voir , n'oubliez pas qu'ilne faut pas lancer le code en mode debug
avec un chrono ..... sinon ça fausse le resultat !

et voici maintenant, le meme code mais multi-threadé

ça décoiffe !

test sur mon petit core duo :

je recherche tout les premiers de 1 a 50 000

- 2eme listing (methode bourrin ) (qui est en fait mon premier code fait )
temps = 159.054 secondes

-1er listing (methode eratosthenes)
temps = 59.079 secondes

et avec le 3em listing ci dessous (méthode eratosthene +multi-thread )
temps = 0.323 seconde !!!!

le code : (cochez Multi-Thread Safe ON )

Code : Tout sélectionner

;***********************************************
;Titre  :nombre_premier _multithread (methode eratothene+multi-thread)
;Auteur  : Zorro
;Date  :06/10/2016
;Heure  :22:54:16
;Version Purebasic :  PureBasic 5.50 (Windows - x86)
;Version de l'editeur :EPB V2.64
; Libairies necessaire : Aucune 
; Mode Multi-Thread Safe  ON
;***********************************************
;{- Enumerations / DataSections
;{ Windows
Enumeration
		#Win
EndEnumeration
;}
;{ Gadgets
Enumeration
		#Editor
		#Button_go
		#Button_stop
		#String_depart
		#String_arrive
		#progress_bar
		#chrono
EndEnumeration
;}
Global start.q,arrive.q,Flag,Flag2,N.q
Global N1.q,N2.q,N3.q,N4.q
Global start1.q,start2.q,start3.q,start4.q
Global Mutex
Global Sortie1.s,Sortie2.s,Sortie3.s,Sortie4.s
Global mem_np=2
Global Addition=2
Declare openwindow_win()
Declare boss1(bidon)
Declare boss2(bidon)
Declare boss3(bidon)
Declare boss4(bidon)

Declare paire_impaire(nombre)
Define.l Event
;}
OpenWindow_Win()
;{- Event loop
Repeat
		Event = WaitWindowEvent(12)
		Select Event
				; ///////////////////
		Case #PB_Event_Gadget
				Select EventGadget()
				Case #Editor
				Case #Button_go
						start.q=val(GetGadgetText(#String_depart))
						N.q=val(GetGadgetText(#String_arrive))
						if paire_impaire(start.q) =#true
								start.q=start.q+1
						Endif
						ClearGadgetItems(#editor)
					;	SetGadgetAttribute(#progress_bar, #PB_ProgressBar_Maximum, N)
						TempsDepart.f = ElapsedMilliseconds() 
						;calldebugger
						;eratosthenes(start,N)
						Mutex = CreateMutex()
						debug "---------------------------------"
						T1=CreateThread(@boss1(),bidon)
						WaitThread(T1)						
						debug Sortie1.s:debug "*********"
						debug "---------------------------------"
						T2=CreateThread(@boss2(),bidon)
						WaitThread(T2)
						debug Sortie2.s:debug "*********"
						debug "---------------------------------"
						T3=CreateThread(@boss3(),bidon)
						WaitThread(T3)
						debug Sortie3.s:debug "*********"
						debug "---------------------------------"
						T4=CreateThread(@boss4(),bidon)
						WaitThread(T4)
						debug Sortie4.s:debug "*********"
						TempsEcoule.f = (ElapsedMilliseconds()-TempsDepart.f  )/1000 ; en secondes
						SetGadgetText(#chrono,"Temp:"+strF( TempsEcoule.f,3 )+" secondes")
						SetGadgetText(#editor, Sortie1.s+Sortie2.s+ Sortie3.s+Sortie4.s)
				Case #String_depart
						start=val(GetGadgetText(#String_depart))
				Case #String_arrive
						arrive=val(GetGadgetText(#String_arrive))
				EndSelect
				; ////////////////////////
		Case #PB_Event_CloseWindow
				Select EventWindow()
				Case #Win
						CloseWindow(#Win)
						Break
				EndSelect
		EndSelect
Forever
;
;}
; procedure zone
Procedure OpenWindow_Win()
		If OpenWindow(#Win, 457, 159, 400, 400, "nombre premier", #PB_Window_SystemMenu|#PB_Window_SizeGadget|#PB_Window_MinimizeGadget|#PB_Window_TitleBar)
				EditorGadget(#Editor, 20, 75, 355, 300)
				ButtonGadget(#Button_go, 20, 5, 85, 30, "GO")
				ButtonGadget(#Button_stop, 130, 5, 85, 30, "Stop")
				StringGadget(#String_depart, 230, 10, 130, 20, "1", #PB_String_Numeric)
				StringGadget(#String_arrive, 230, 40, 130, 20, "80000000", #PB_String_Numeric)				
				TextGadget(#chrono,20,40,200,15,"Temp:"+"0.00")
		EndIf
EndProcedure
Procedure boss1(bidon)
		Sortie1.s=""
		LockMutex(Mutex)
		if Start<2 
				Sortie1.s=Sortie1.s+"2"+" "+chr(10)
		Endif
		start1=Start 
		N1=N/4
		debug " de "+str(start1)+"a "+str(N1)
		Dim N(N1+10); 
		
		For X = start1 To N1 Step 2      
				Divis = 0
				For Y = 2 To Sqr(X)
						If mod(X , Y )= 0 
								Divis + 1
						EndIf
				Next  Y
				If Divis = 0 	and x<>1
						Sortie1.s=Sortie1.s+Str(X)+" "+chr(10)
				EndIf
		Next  X 
		UnlockMutex(Mutex)
EndProcedure
;
Procedure boss2(bidon)
		Sortie2.s=""
		LockMutex(Mutex)
		start2=Start+(N/4)
		N2=N-((N/4)*2)
		debug " de "+str(start2)+"a "+str(N2)
		Dim N(N2+10); 
		For X = start2 To N2 Step 2           
				Divis = 0
				For Y = 2 To Sqr(X)
						If mod(X , Y )= 0 
								Divis + 1
						EndIf
				Next  Y
				If Divis = 0 				
						Sortie2.s=Sortie2.s+Str(X)+" "+chr(10)
				EndIf
		Next  X 
		UnlockMutex(Mutex)
EndProcedure
;
Procedure boss3(bidon)
		Sortie3.s=""
		LockMutex(Mutex)
		start3=Start+((N/4)*2)
		N3=N-((N/4))
		debug " de "+str(start3)+"a "+str(N3)
		Dim N(N3+10); 
		For X = start3 To N3 Step 2           
				Divis = 0
				For Y = 2 To Sqr(X)
						If mod(X , Y )= 0 
								Divis + 1
						EndIf
				Next  Y
				If Divis = 0 				
						Sortie3.s=Sortie3.s+Str(X)+" "+chr(10)
				EndIf
		Next  X 
		UnlockMutex(Mutex)
EndProcedure
;
Procedure boss4(bidon)
		Sortie4.s=""
		LockMutex(Mutex)
		start4=Start+((N/4)*3)
		N4=N
		debug " de "+str(start4)+"a "+str(N4)
		Dim N(N+10); 
		For X = start4 To N4 Step 2           
				Divis = 0
				For Y = 2 To Sqr(X)
						If mod(X , Y )= 0 
								Divis + 1
						EndIf
				Next  Y
				If Divis = 0 				
						Sortie4.s=Sortie4.s+Str(X)+" "+chr(10)
				EndIf
		Next  X 
		UnlockMutex(Mutex)
EndProcedure

Procedure paire_impaire(nombre)
		If nombre % 2 <> 0  ; nombre impaire
				retour = #false
		Else ; nombre paire
				retour= #True ; paire
		EndIf
		ProcedureReturn retour
EndProcedure

; Epb

[JohnJohnsonSHERMAN]

Pas mal... sur mon pc portable ca met 1.751 secondes. Par contre j'ai été obligé de créér une ProgressBar manuellement, puisque tu fais appel à SetGadgetAttribute(#progress_bar...) dans ton code, sans avoir créé ladite progressbar avant Un vieux renard comme toi ne devrait plus se laisser prendre à cela
C'est bizarre aussi que ,malgré les threads, lorsque l'opération est lancée, le programme cesse de répondre... le but des threads est -entre autre- d'éviter cela. Sinon c'est trés intéresant, mais mes conaissances en nombre premiers se limitent a
-Pas de diviseur autre que 1 ou lui même
-Un tas de propriétés bizarres et inconnues de mon cerveau

PS : j'ai un AMD A8

[Zorro]

Pas mal... sur mon pc portable ca met 1.751 secondes. Par contre j'ai été obligé de créér une ProgressBar manuellement, puisque tu fais appel à SetGadgetAttribute(#progress_bar...) dans ton code, sans avoir créé ladite progressbar avant Un vieux renard comme toi ne devrait plus se laisser prendre à cela

en fait , je l'ai retiré , car le progress bar dans un thread, chez moi ça bloque tout !!
( d'ailleurs meme l'attribution dans un gadget (SetGadgetText() par exemple ) du moment que c'est dans une procedure threadée
ça bloque tout !! )

C'est bizarre aussi que ,malgré les threads, lorsque l'opération est lancée, le programme cesse de répondre... le but des threads est -entre autre- d'éviter cela.

pas du tout !!
un thread permet de faire faire un sous calcul ou un calcul en parrallele au fil principale (bref executer une procedure...)
on peut aussi s'en servir pour repondre aux gadgets (windowEvent() , mais c'est pas son but premier !
pour eviter les pertes de temps , dans cette version , j'ai desactivé le progressbar et la surveillance des gadgets
donc le bouton Stop ne marche pas non plus , c'est fait expres
le prg semble figer, mais c'est parceque tout le processeur s'occupe de la tache pour laquel on le sollicite

[Micoute]

Du très grand art.

[JohnJohnsonSHERMAN]

En effet... j'aurais jamais su calculer un nombre premier, moi....

[Zorro]

Merci

petite aparté , un pote m'avais parlé de certains nombres, qui ne sont pas forcement premier
mais qui ont une particularité qui les rends tres rare !

la particularité : c'est que ce nombre multiplié par lui meme donne un resultat qui contient ce nombre a la fin

exemple :
1 Multiplie par 1 = 1
5 Multiplie par 5 = 25
6 Multiplie par 6 = 36
25 Multiplie par 25 = 625
76 Multiplie par 76 = 5776
376 Multiplie par 376 = 141376
625 Multiplie par 625 = 390625
9376 Multiplie par 9376 = 87909376
90625 Multiplie par 90625 = 8212890625
109376 Multiplie par 109376 = 11963109376
890625 Multiplie par 890625 = 793212890625
2890625 Multiplie par 2890625 = 8355712890625
7109376 Multiplie par 7109376 = 50543227109376



etc ....
plus on va vers les grands nombre, plus ils sont rare , voici un petit code en mode console
pour les faire apparaître :

qui va trouver le plus grand ??

Code : Tout sélectionner

; Code par Zorro
Resultat = OpenConsole()

debut:
a.q=a.q+1
ConsoleTitle(Str(a.q))
b.s=Str(a.q)

long=Len(b.s)
If Val(Right(Str(a.q*a.q),long))=a.q
sortie.s=sortie.s+Str(a.q)+" Multiplie par "+Str(a.q)+" = "+Str(a.q*a.q)+chr(10)
		Print(Str(a.q))
		Print(" Multiplie par ")
		Print(Str(a.q))
		Print(" = ")
		Print(Str(a.q*a.q))
		PrintN("")
		SetClipboardText(sortie.s)
EndIf
Delay(1)
Goto debut 

[JohnJohnsonSHERMAN]

Il mouline depuis ce midi, et il m'a trouvé 12890625 Multiplie par 12890625 = 166168212890625.
Pour l'instant je suis donc en tête avec seulement une valeur (en ce moment il en est à 15690734). J'ai l'impression que changer le titre de la fenêtre lui fait perdre un peu de temps.

Bon je vais le laisser tourner jusqu'a 8h et aprés on verra

Edit : courbe des valeurs trouvées jusqu'à présent :
(lien de rechange).
Je pronostique le nombre dobrien (j'ai pas trouvé d'autre nom ) suivant aux alentours de 26000000 +- 1000000... Y'a l'temps...

[Zorro]

je ne sais pas s'ils sont prédictibles ! ?

on vois une certaines logique :

376
625
9376
90625
109376
890625
2890625
7109376

mais de la a pouvoir les prédires ..... pas evident