Turbo nombres premiers

DjPoke

Bonsoir,

Je viens de terminer un programme de calcul (très ?) rapide de nombres premiers, basé sur mes propres recherches.
Je voudrais savoir si quelqu'un pourrait le tester, pour y trouver une éventuelle faille, mais aussi pour savoir s'il existe des algorithmes aussi rapides.

Merci d'avance.

Voici le code :

Code:

OpenConsole()
Repeat
PrintN("Entrez un nombre a verifier :")
a$=Input()
nb.q=Val(a$)
Premier=1
tt.f=ElapsedMilliseconds()
i.q=2
j.q=3
While (j.q*j.q)<=nb.q
  j.q=j.q+1  
Wend
While i.q<j.q
  If (nb.q % i.q)=0
    Premier=0
    j.q=nb.q/i.q
    PrintN(Str(i.q)+" * "+Str(j.q))
  EndIf
  i.q=i.q+1
Wend
tt.f=(ElapsedMilliseconds()-tt.f)/1000.000
If Premier=1
  PrintN("Ce nombre est PREMIER !")
Else
  PrintN("Ce nombre n'est PAS PREMIER !")
EndIf
PrintN("Temps de verification : "+StrF(tt.f))
PrintN("")
PrintN("Voulez vous verifier un autre nombre ? (o/n)")
a$=Input()
If LCase(a$)<>"o"
  CloseConsole()
  End
EndIf
PrintN("")
ForEver

Fig · **Inscription:** Jeu 14/Oct/2004 19:48 **Messages:** 420

Déja quand le nombre se finit par 0-5 ou un chiffre pair, il ne peut pas être premier... Or ton programme se lance quand même dans des calculs interminables

Tu peux aussi virer tout les nombre qui ne satisfont pas au petit théorème de Fermat, tu es sûr qu'ils ne sont pas premiers.

Sinon, pourquoi tu ne fais pas une racine carré arrondie au dessus pour ton premier while/wend ?

Voila, sinon c'ets vrai que c'est déja assez rapide.

(punaise on a plus de amileys, il se passe quoi là ??)

zaphod · **Inscription:** Dim 07/Déc/2008 9:32 **Messages:** 135

graph100 · **Inscription:** Sam 21/Mai/2005 17:50 **Messages:** 941

attention la =)

Va pas dire que PB est lent !!
quand je compile 3 - 4 fois, je tombe entre 0.67 sec et 0.60 sec

mais j'ai modifié le code : tu utilises des type trop grand ! ça ralenti le truc alors que c'est pour stocker des booléens

Code:

; algo nat the great pour blitzmax
; port en pb by zaphod - 23/05/2011
; en blitzmax = 0.838 sec
; en pb = 1.42 sec
; pentium 4 - 3 Ghz
; 
; modifier par graph100
; avec la modif : 0.67 sec
; core2duo 2.50Ghz
; 
; >>>> Compiler sans le debuger
;
Define num.i = 15485864

num + 1

Define sqrnum.i = Sqr(num) + 1

Dim PrimeFlags.b(num)
Dim Primes.i(num)
Define tim.i,count.i
Define mill.i = ElapsedMilliseconds()


For x = 2 To sqrnum
   If primeflags(x) = #False
      Primes(count) = x
      count + 1     
      
      tim = x
      Repeat
         tim + x
         primeflags(tim) = #True
      Until x + tim >= num
   EndIf
Next


For y = sqrnum To num - 1
   If primeflags(y) = #False
      Primes(count) = y
      
      count + 1      
   EndIf
Next
mill = ElapsedMilliseconds()-mill



MessageRequester("", StrF(mill / 1000.0) + " seconds " + Str(count) + " primes found!")

DjPoke

Merci pour vos réponses.
En tout cas, cela m'a fait réaliser à quel point PB est plus rapide que les autres.

Le Soldat Inconnu

De cette manière, c'est encore plus rapide

Et ça corrige un bug sur la dernière valeur qui n'était pas un nombre premier dans le précédent algo, essai en visualisant les valeurs avec Num = 2000 et tu verra que 2000 est considéré comme nombre premier ...

0.326s chez moi sur un I5 2.67 MHz, vive PB.
0.5s avec ton code

Code:

; algo nat the great pour blitzmax
; port en pb by zaphod - 23/05/2011
; en blitzmax = 0.838 sec
; en pb = 1.42 sec
; pentium 4 - 3 Ghz
;
; >>>> Compiler sans le debuger
;
Define num.i = 15485864
Define sqrnum.i = Sqr(num)+1
Dim PrimeFlags.b(num)
Dim Primes.i(num)
Define tim.i,count.i = 2
Define mill.i = ElapsedMilliseconds()
;
For x = 3 To sqrnum Step 2
      If PrimeFlags(x) = #False 
            tim = x + x
            Repeat
                  PrimeFlags(tim) = #True
                  tim + x
            Until tim >= num
      EndIf
Next 
;Local count:Int
Primes(1) = 2
For x = 3 To num Step 2
      If PrimeFlags(x) = #False 
            Primes(count) = x
            count+1   
            Debug x
      EndIf
Next
mill = ElapsedMilliseconds()-mill
;
MessageRequester("",StrF(mill/1000.0) +" seconds "+ Str(count)+" primes found!")

graph100 · **Inscription:** Sam 21/Mai/2005 17:50 **Messages:** 941

en fait j'avais oublié de compter 2 dans l'algo :oops:

sinon le dernier nb premier était bon dans ma version

et sur mon pc, il n'y a pas de différence nette entre ton algo (@lsi) et le mien, faudrait que je teste avec un plus grand nombre.
Mais effectivement ça va plus vite !

teste avec la modif suivante ^^ :

Code:

; algo nat the great pour blitzmax
; port en pb by zaphod - 23/05/2011
; en blitzmax = 0.838 sec
; en pb = 1.42 sec
; pentium 4 - 3 Ghz
;
; >>>> Compiler sans le debuger
;
Define num.i = 15485864
Define sqrnum.i = Sqr(num)+1
Dim PrimeFlags.b(num)
Dim Primes.i(num)
Define tim.i,count.i = 2
Define mill.i = ElapsedMilliseconds()
;
For x = 3 To sqrnum Step 2
   If PrimeFlags(x) = #False
      Primes(count) = x
      count+1   
      
      tim = x + x
      Repeat
         PrimeFlags(tim) = #True
         tim + x
      Until tim >= num
   EndIf
Next
;Local count:Int

Primes(1) = 2
For y = x To num Step 2
   If PrimeFlags(y) = #False
      Primes(count) = y
      count+1   
   EndIf
Next
mill = ElapsedMilliseconds()-mill
;
MessageRequester("",StrF(mill/1000.0) +" seconds "+ Str(count)+" primes found!")

Le Soldat Inconnu

ça devrait être plus rapide mais je ne vois aucune différence. j'ai testé en mettant Num = 200000000

graph100 · **Inscription:** Sam 21/Mai/2005 17:50 **Messages:** 941

bah, le gain doit être négligeable ! Pense-tu qu'on peut faire plus rapide en assembleur ??

>< je test l'extension de erix14, c'est juste énorme ><

http://www.purebasic.fr/french/viewtopic.php?f=8&t=9608&start=75

Starwolf20 · **Inscription:** Mar 01/Sep/2009 18:39 **Messages:** 7

Salut !!

zaphod · **Inscription:** Dim 07/Déc/2008 9:32 **Messages:** 135

graph100 · **Inscription:** Sam 21/Mai/2005 17:50 **Messages:** 941

Ça dépend peut être des différents processeurs qui ne sont pas gérer pareil par les langages ?
Faudrait avoir le truc en blitzmax pour pouvoir comparer sur différents pc

Starwolf20 · **Inscription:** Mar 01/Sep/2009 18:39 **Messages:** 7

L'algo de Nat the great est tres elegant, compact et efficace.

A titre d'information et puisque on a parlé d'assembleur, j'ai tenté de decortiquer le code generé par PB.
Sans être un UBER specialiste, je l'ai trouvé tres bon.
Atitre d'exemple, voici ce que ca donne en optimisant une partie du code.
Nb : Activez l'assembleur en ligne dans les options du compilateur.

Code:

; algo nat the great pour blitzmax
; port en pb by zaphod - 23/05/2011
; en blitzmax = 0.838 sec
; en pb = 1.42 sec
; pentium 4 - 3 Ghz
;
; >>>> Compiler sans le debuger
;
Define num.i = 15485864
Define sqrnum.i = Sqr(num)+1
Dim PrimeFlags.b(num)
Dim Primes.i(num)
Define tim.i,count.i = 2
Define mill.i = ElapsedMilliseconds()
;
For x = 3 To sqrnum Step 2
      If PrimeFlags(x) = #False
            Primes(count) = x
            count+1   
            
            tim = x + x
;-------------------------------------- Partie du code remplacé en assembleur            
;;;            Repeat;
;;;                  PrimeFlags(tim) = #True
;;;                  tim + x
;;;               Until tim >= num
                           
          ; Repeat
             MOV    ebx,dword [v_tim]
             MOV    ebp,dword [a_PrimeFlags]
          Repeat5:
        ; PrimeFlags(tim) = #True
          ;MOV    ebx,dword [v_tim]        ; deplacé en dehors de la boucle
          ;MOV    ebp,dword [a_PrimeFlags] ; deplacé en dehors de la boucle
             MOV    byte [ebp+ebx],1
        ; tim + x
          ;MOV    ebx,dword [v_tim]
             ADD    ebx,dword [v_x]
          ;MOV    dword [v_tim],ebx        ; deplacé en dehors de la boucle
        ; Until tim >= num
          ;MOV    ebx,dword [v_tim]         
             CMP    ebx,dword [v_num]
             JL    l_repeat5
        ;_Until5:
        MOV    dword [v_tim],ebx
;--------------------------------------    
        
      EndIf
Next
;Local count:Int

Primes(1) = 2
For y = x To num Step 2
      If PrimeFlags(y) = #False
            Primes(count) = y
            count+1   
      EndIf
Next
mill = ElapsedMilliseconds()-mill
;
MessageRequester("",StrF(mill/1000.0) +" seconds "+ Str(count)+" primes found!")

graph100 · **Inscription:** Sam 21/Mai/2005 17:50 **Messages:** 941

bah 0.5 sec pour moi

ça va plus vite effectivement, chez LSI, ça doit dépoter vu qu'il faisait 0.3 sec avant

Le Soldat Inconnu

entre 0.280 / 0.296 :mrgreen:

PureBasic

Turbo nombres premiers

Qui est en ligne