[TUTO]-Calcul des nombres premier

Informations pour bien débuter en PureBasic
Avatar de l’utilisateur
flaith
Messages : 1487
Inscription : jeu. 07/avr./2005 1:06
Localisation : Rennes
Contact :

[TUTO]-Calcul des nombres premier

Message par flaith »

Bonjour,

je me disais qu'un tutoriel simple concernant un domaine connu de tous serait le bienvenu pour un débutant
Donc voila ce petit bout de code, commenté et, je l'espère, compréhensible par tous

Code : Tout sélectionner

; Note: le débogueur doit être activé
; Affiche la liste des nombres premier allant de 1 à 'nombre_total'
nombre_total = 200

Debug "Liste des nombres premier allant de 1 à "+Str(nombre_total)
For nbprem = 1 To nombre_total
  nb_division = 0
  For x = 1 To nombre_total
    If nbprem % x = 0                 ;Résultat du reste de la division (modulo) = 0
      nb_division + 1                 ;ajoute 1 au nombre de division actuel
    EndIf
  Next
  If nb_division = 2                  ;Divisible par 1 et par lui même (donc 2 fois)
    Debug Str(nbprem)                 ;Alors c'est un nombre premier
  EndIf
Next
beruska
Messages : 21
Inscription : sam. 28/mai/2011 12:32

Re: [TUTO]-Calcul des nombres premier

Message par beruska »

J'ai bien aimé l'algorithme pour le calcul des nombres premiers; l'inconvénient est que pour les grands nombres il faut un temps fou. A chaque itération il faut limiter la recherche à la sqr du nombre qui diminue à chaque division. Et encore plus vite en travaillant seulement sues les nombres impairs. A+

Code : Tout sélectionner

; PB 4.51 - Recherche de nombres premiers - by beruska

premier = 73918
dernier = premier + 3000               

debut = ElapsedMilliseconds()
Debug "Nombres premiers entre " + Str(premier) + " et " + Str(dernier)

  If premier % 2 = 0                   ; vérifie si le nombre p est pair
    premier + 1                        ; on part de l'impair suivant (on sait que 2 est premier)
  EndIf 
  
  For n = premier To dernier Step 2   ; on ne travaille que sur les nombres impairs
    
    flag = #True
    x = 3                              ; on fixe le premier diviseur en x
            
    While x <= Int(Sqr(n))            ; on limite la recherche à la Sqr du nombre [car A*B = B*A]
      If n % x = 0                    ; si n est divisible par x, ce ne sera pas un nombre premier
        flag = #False                  ; flag nécessaire pour éviter l'affichage
        Break                         ; on quitte la boucle While... Wend
      Else
        x + 2                          ; sinon, on augmente le diviseur de deux unités 
      EndIf
    Wend
                       
    If flag = #True                    
;      If n = 3 : Debug n-1 : cont +1: EndIf   ; pour afficher le nombre 2
      Debug n                         ; on affiche le nombre qui est "premier"
      cont +1                         ; compteur d'itérations
    EndIf 
    
  Next 
  
  Debug "Trouvés " + Str(cont) + " nombres premiers in " + Str(ElapsedMilliseconds() - debut) + " millisecondes"
  
End
Répondre