Nombres premiers

[Le Soldat Inconnu]

un codes qui permet de trouver des nombres premiers puis les mets sous forme de data dans un code.

Code : Tout sélectionner

; Recherche de nombres premiers

#Max = 10000
#Ligne = 40

NewList Nb.l()


For n = 3 To #Max Step 2
  
  NbPremier = 1
  ResetList(Nb())
  While NextElement(Nb())
    If n % Nb() = 0
      NbPremier = 0
      Break
    EndIf
  Wend
  
  If NbPremier
    AddElement(Nb())
    Nb() = n
    Debug Str(CountList(Nb())) + " = " + Str(n)
  EndIf
  
Next


If CreateFile(0, "Nb Premier [Data].pb")
  WriteStringN("#NbData_NbPremier = " + Str(CountList(Nb())))
  WriteStringN("DataSection")
  WriteString("  NbPremier :")
  Ligne = #Ligne
  ResetList(Nb())
  While NextElement(Nb())
    Ligne + 1
     
    If Ligne < #Ligne
      WriteString(", " + Str(Nb()))
    Else
      Ligne = 0
      WriteStringN("")
      WriteString("    Data.l " + Str(Nb()))
    EndIf
  Wend
  WriteStringN("")
  WriteString("EndDataSection")
  CloseFile(0)
EndIf

Debug "Terminé"

[Le Soldat Inconnu]

j'ai ajouté des explications

Code : Tout sélectionner

; Auteur : Le Soldat Inconnu
; Version de PB : 3.9
; 
; Explication du programme :
; Recherche de nombre premier

; Comment savoir si un nombre est premier ?
; Un nombre est premier si on ne peut le diviser sous la forme d'entier que par lui même
; Exemple :
; 3 / 2 = 1.5 OK
; 3 / 3 = 1 OK
; 3 / 4 = 0.75 OK
; 
; 4 / 2 = 2 Mauvais
;
; Donc 3 est un nombre premier et 4 n'est pas un nombre premier


#Max = 10000 ; On cherche les nombres premier entre 2 et 10000

NewList Nb.l() ; On crée une liste dans laquelle on va stocker les nombres premiers

; On ajoute 2 directement à la liste des nombres premiers
AddElement(Nb())
Nb() = 2
; En effet 2 est le seule nombre pair premier car tous les autres nombres pairs sont divisibles par 2
; Pour optimiser le code, on ne traite que les nombres impairs
; C'est pour cela que la boucle commence à 3 et a un pas de 2

; Une autre propriété permet de simplifier, la voici :
; Un nombre est premier si celui-ci n'est pas divisible sous la forme de nombre entier par un autre nombre premier de valeur inférieure
; Exemple :
; 3, 5, 7, 11, 13, 17, 19, 23, 29 sont des nombres premiers
; On va vérifier que 29 est bien premier, déjà il est impair
; 29 / 3 OK
; 29 / 5 OK
; 29 / 7 OK
; 29 / 11 OK
; 29 / 13 OK
; 29 / 17 OK
; 29 / 19 OK
; 29 / 23 OK
; On vérifie avec les autres valeurs impaires
; 29 / 9 OK 
; Car 9 n'est pas premier donc est divisible,  29 / 9 = 29 / 3 * 1/ 3 donc 29 / 9 revient à tester 29 / 3
; C'est l'explication de la propriété ci dessus.
; 29 / 15 OK 
; 29 / 21 OK
; 29 / 25 OK
; 29 / 27 OK
; Donc 29 est bien premier
; On vient d'économiser 5 tests pour la valeur 29, alors pour des valeurs supérieur à 1000, cette optimisation est très intéressantes

For n = 3 To #Max Step 2
  
  NbPremier = 1
  
  ResetList(Nb())
  While NextElement(Nb()) ; pour chaque nombre premier trouvé
    If n % Nb() = 0 ; On regarde si la division de la valeur par le nombre premier ne donne pas de reste
      NbPremier = 0 ; Si oui, la valeur est divisible est nombre entier donc ce n'est pas un nombre premier
      Break ; On quitte la boucle, il est inutile de faire les tests suivants
    EndIf
  Wend
  
  If NbPremier ; Si le nombre est premier
    AddElement(Nb()) ; On l'ajoute à la liste
    Nb() = n
  EndIf
  
Next

; On affiche les nombres premiers trouvés
ResetList(Nb())
While NextElement(Nb())
  Debug Str(CountList(Nb())) + " = " + Str(Nb())
Wend

[Frenchy Pilou]

je crois que la formule
F(n) = 2 + (2n! Mod( n+1) ) donne tous les nombres premiers, et uniquement les nombres premiers, pour tout entier naturel n>1

[filperj]

Intéressant, mais soit tu as fait une faute de frappe, soit le "!" signifie autrechose que "xor" (mais alors quoi?).

Ou alors Mod est devenu unaire pendant que j'avais le dos tourné

[Oliv]

Le ! signifie factorielle à mon avis (enfin en théorie) c'est pour ça que je ne vois pas bien ce qu'il fait la vu que factorielle 2 c'est 2

Sinon factorielle n c'est :

Code : Tout sélectionner

n! = n * (n-1) * (n-2) *.........*3*2*1

Donc 5! = 5 * 4 * 3 * 2 * 1 = 120 par contre par convention 0! = 1
Et si le ! de Frenchy Pilou veut dire autre chose, je ne sais pas

[Frenchy Pilou]

AAAAAAAAAHhhhhhhhhhh
F(n) = 2 + (2n! Mod( n+1) )

Le ! est bien "factoriel" mais la gaffe c''est que j'avais oublié un terme

C'est réparé
je vous donne le lien http://fr.wikipedia.org/wiki/Nombre_premier
Mais...
M'a l'air fausse, qu'en pensez-vous ?

[Le Soldat Inconnu]

elle done des nombre premier mais pas tous visiblement.

en plus, pour n = 5, on obtient 42, c'est pas un nombre premier

[Oliv]

Sinon tous les nombres premiers supérieurs à 2 sont donnés par 4n + 1 et 4n + 3 . Antention, même si ça donne tous les nombres premiers, ça ne donne pas que des nombres premiers car 15 = 4 * 3 + 3