Crible Ératosthènes

[Heis Spiter]

Tout le monde connait cet algo qui sert à trouver les nombres premier inférieurs à un certain nombre. Par besoin pour un programme, je l'ai écrit en Pure pour qu'il donne un nombre premier au pif entre 2 et le nombre donné.

Code : Tout sélectionner

Structure Numbers
  Number.b
  Tried.b
EndStructure
NewList Numbers.Numbers()

Procedure IsDivisible(Number1, Number2)
  
  Result = Number1 % Number2
  If Result = 0 : ToReturn = 1
  Else : ToReturn = 0
  EndIf
  ProcedureReturn ToReturn
  
EndProcedure

Procedure RandomSieveEratosthenes(Max)
  
  Maximum = Random(Max)
  If Maximum < 2
    Maximum = 2
  EndIf
  ; Step 1
  For k = 2 To Maximum
    AddElement(Numbers())
    Numbers()\Number = k
  Next k
  ;Step 2/4
  Repeat
    ResetList(Numbers())
    Repeat 
      NextElement = NextElement(Numbers())
      If NextElement
        If Numbers()\Tried = 0
          i = Numbers()\Number
          Numbers()\Tried = 1
          Break
        EndIf
      EndIf
    Until NextElement = 0
    If Pow(i, 2) > Maximum+1
      Break
    EndIf
    ; Step 3
    For k = i To CountList(Numbers())*2
      NextElement(Numbers())
      If IsDivisible(Numbers()\Number, i)
        DeleteElement(Numbers(), 1)
      EndIf
    Next k
  ForEver
  Get = Random(CountList(Numbers())-1)
  SelectElement(Numbers(), Get)
  ToReturn = Numbers()\Number
  ClearList(Numbers())
  ProcedureReturn ToReturn
  
EndProcedure

Vala Toute remarque est bonne.

[Flype]

heu juste pour le fun :

Code : Tout sélectionner

Procedure IsDiv0(a, b) 
  c = a % b 
  If c = 0
    d = 1 
  Else
    d = 0 
  EndIf 
  ProcedureReturn d
EndProcedure 

Procedure IsDiv1(a, b)
  If (a % b)
    ProcedureReturn #False
  EndIf
  ProcedureReturn #True
EndProcedure 

Procedure IsDiv2(a, b)
  ProcedureReturn 1 - (a % b And 1)  
EndProcedure

Procedure IsDiv3(a, b)
  If (a % b)
    ProcedureReturn #False
  Else
    ProcedureReturn #True
  EndIf
EndProcedure

x=99
y=3
Debug IsDiv0(x,y)
Debug IsDiv1(x,y)
Debug IsDiv2(x,y)
Debug IsDiv3(x,y)

laquelle tu préfères ?

[Heis Spiter]

Ah . Hier soir, cherchant à optimiser la fonction ci-dessus, plongé dans un bouquin de maths, j'ai trouvé l'optimisation extrême (mais pas forcément fiable) pour la fonction. Utiliser le boulot d'Euler. À savoir que des nombres permiers peuvent être trouvés à l'aide de

On pose n un nombre entier différent de 41.
Alors, le nombre premier vaudra n²-n+41

Code : Tout sélectionner

Procedure RandomPrimeEuler(Maximum) ; Generates a random prime number using Euler demonstration (fast, but not sure)
  Start :
  Number = Random(Sqr(Maximum))
  If Number = 41
    Goto Start
  EndIf
  ProcedureReturn Number*Number-Number+41
EndProcedure

C'est-y pas beau ? Je l'ai envoyé pour la mise à jour de la PBOSL.

[djes]

[Chris]

Je sens que je vais passer pour une buse, mais....

Ca sert à quoi?

[Dr. Dri]

c'est pas plus simple encore comme ca ?

Code : Tout sélectionner

Procedure RandomPrimeEuler(Maximum) ; Generates a random prime number using Euler demonstration (fast, but not sure)
  Repeat
    Number = Random(Sqr(Maximum))
  Until Number <> 41
  ProcedureReturn Number*Number-Number+41
EndProcedure

Dri

[djes]

Oulà! Une boucle? Pourquoi tu testes pas si c'est 41 et que tu ajoutes 1, ou un autre random?

[Heis Spiter]

@Chris : À générer un nombre premier de façon aléatoire.
@Dr. Dri : L'admin de PBOSL vient de me propose la même chose
@djes : comprend pas ta question

[Chris]

@Chris : À générer un nombre premier de façon aléatoire.

Ca, j'avais bien compris (y m'prend pour un abruti, ou quoi, lui? )

Ma question est : Ca sert à quoi, les nombres premiers en programmation?

[Pierre]

par exemple c'est utilisé en cryptographie...cherche sur google ^^

[Heis Spiter]

C'est utilisé dans l'algorithme de cryptage le plus utilisé le RSA. Qui compte sur la difficulté de factoriser des nombres entiers en facteurs premiers... Mais depuis peu, les avancés mathématiques ont fait que on y arrive de plus en plus facilement...

[djes]

Heis>C'était rapport au code de Dri!

[Dr. Dri]

@djes
je n'ai fait que virer la "boucle goto" de Heis ^^
ca fait tout de même plus court et plus propre

après pour ce qui est de "to loop or not to loop" c'est une autre histoire ^^

Soit-dit en passant, j'ai pu obtenir un nombre plus grand que le maximum. C'est normal ?

Dri

[Heis Spiter]

Non . Tu obtiens un nombre supérieur au Max, si tu utilise un nombre Max inférieur à 41.

[Dr. Dri]

ah nan c'est avec 1000 que j'ai réussi a obtenir plus !!

Code : Tout sélectionner

Repeat
  a = RandomPrimeEuler(1000)
  Debug a
Until a > 1000

Dri