[Ex] Calcul de nombre premiers

Partagez vos scripts, et vos applications AutoIt.
Règles du forum
.
Répondre
Avatar du membre
N3mesis
Niveau 2
Niveau 2
Messages : 17
Enregistré le : ven. 01 févr. 2013 11:20
Status : Hors ligne

[Ex] Calcul de nombre premiers

#1

Message par N3mesis »

Et voila, comme promis voici un programme (avec GUI) permettant de chercher (et éventuellement enregistrer) les nombres premiers d'un interval donné.
Si vous avez des questions ou idées d'améliorations n'hesitez pas.

Code : Tout sélectionner

#cs ----------------------------------------------------------------------------

 AutoIt Version: 3.3.8.1
 Author:         N3mesis

 Script Function:
    Trouver les nombres premiers d'un interval donné

#ce ----------------------------------------------------------------------------

#include <ButtonConstants.au3>
#include <EditConstants.au3>
#include <GUIConstantsEx.au3>
#include <GUIListBox.au3>
#include <ProgressConstants.au3>
#include <StaticConstants.au3>
#include <WindowsConstants.au3>

#Region ### START Koda GUI section ### Form=
$Form1 = GUICreate("Nombres premiers", 615, 532, 192, 124)
$Label1 = GUICtrlCreateLabel("Nombres premiers", 10, 10, 329, 49)
GUICtrlSetFont(-1, 30, 400, 0, "Arial")
$Group1 = GUICtrlCreateGroup("Options", 375, 65, 226, 246)
$Group3 = GUICtrlCreateGroup("Interval", 385, 85, 206, 126)
$Label2 = GUICtrlCreateLabel("Minimum :", 400, 105, 63, 20)
GUICtrlSetFont(-1, 10, 400, 0, "MS Sans Serif")
$Label3 = GUICtrlCreateLabel("Maximum :", 400, 155, 67, 20)
GUICtrlSetFont(-1, 10, 400, 0, "MS Sans Serif")
$Input1 = GUICtrlCreateInput("2", 410, 125, 171, 21) ;minimum
$Input2 = GUICtrlCreateInput("", 410, 175, 171, 21) ;maximum
GUICtrlCreateGroup("", -99, -99, 1, 1)
$Checkbox1 = GUICtrlCreateCheckbox("Enregistrer les resultats dans un fichier", 385, 216, 206, 26)
$Label4 = GUICtrlCreateLabel("Chemin du fichier :", 385, 245, 206, 22)
$Button3 = GUICtrlCreateButton("Parcourir", 430, 270, 116, 31)
GUICtrlCreateGroup("", -99, -99, 1, 1)
$Group2 = GUICtrlCreateGroup("Resultat", 10, 65, 346, 451)
$List1 = GUICtrlCreateList("", 20, 85, 326, 422,$WS_VSCROLL)
GUICtrlCreateGroup("", -99, -99, 1, 1)
$Button1 = GUICtrlCreateButton("Lancer", 385, 440, 206, 61)
$Progress1 = GUICtrlCreateProgress(380, 345, 211, 56)
$Button2 = GUICtrlCreateButton("Help", 405, 10, 171, 46)
GUISetState(@SW_SHOW)
#EndRegion ### END Koda GUI section ###

GUICtrlSetState($Button3,$GUI_DISABLE)
While 1
    Sleep(10)
    $nMsg=GUIGetMsg()
    Switch $nMsg
        Case $GUI_EVENT_CLOSE
            Exit
        Case $Checkbox1
            If GUICtrlRead($Checkbox1)=$GUI_UNCHECKED Then
                GUICtrlSetState($Button3,$GUI_DISABLE)
            ElseIf GUICtrlRead($Checkbox1)=$GUI_CHECKED Then
                GUICtrlSetState($Button3,$GUI_ENABLE)
            EndIf
        Case $Button2 ;help
            MsgBox(0+64,"","Un nombre premier est un entier naturel qui admet exactement " & _
                "deux diviseurs distincts entiers et positifs (qui sont alors 1 et lui-même)." & _
                @CRLF & "Cette définition exclut 1, qui n'a qu'un seul diviseur entier positif." & _
                @CRLF & @CRLF & "Ce programme permet de calculer les differents nombres premiers d'un interval donné.")
        Case $Button3 ;chemin du fichier ou enregistrer
            $file_path=FileOpenDialog("",@DesktopDir,"Texte (*.txt)",8)
            GUICtrlSetData($Label4,"Chemin du fichier : " & $file_path)
        Case $Button1
            ;verification des conditions avant lancement du calcul
            $min=GUICtrlRead($Input1)
            $max=GUICtrlRead($Input2)
            If GUICtrlRead($Checkbox1)=$GUI_CHECKED And GUICtrlRead($Label4)="Chemin du fichier :" Then
                MsgBox(0,"","Veuillez choisir un fichier ou seront enregistrées les données")
            ElseIf StringIsDigit($min)=0 Or StringIsDigit($max)=0 Then
                MsgBox(0,"","Les bornes superieures et inferieures de l'interval doivent etre des nombres entiers")
            Else
                $min=Int($min)
                $max=Int($max)
                If $min=0 or $min=1 Then
                    $min=2
                    GUICtrlSetData($Input1,$min)
                ElseIf $min>$max Then
                    $temp=$max
                    $max=$min
                    $min=$temp
                    GUICtrlSetData($Input1,$min)
                    GUICtrlSetData($Input2,$max)
                Else ;Partie principale du programme
                    $Error=0
                    Dim $array[1]=[""]
                    $n=$min
                    While $n<=$max
                        GUICtrlSetData($List1,"Recherche des nombres premiers dans l'interval " & "[" & $min & "," & $max &"]")
                        GUICtrlSetData($Progress1,($n*100)/($max-$min))
                        $nMsg=GUIGetMsg()
                        If $nMsg=$GUI_EVENT_CLOSE Then ;permet de sortir de la boucle --> enregistre ou le programme a été interrompu
                            $Error=1
                            GUICtrlSetData($List1,"Procedure de calcul interrompue à " & $n)
                            ExitLoop
                        EndIf
                        $p=Ispremier($n)
                        If $p=True Then
                            GUICtrlSetData($List1,$n)
                            $temp=UBound($array)
                            ReDim $array[$temp+1]
                            $array[$temp]=$n
                        EndIf
                        $n=$n+1
                    WEnd
                    $temp=UBound($array)-1
                    $array[0]=$temp
                    GUICtrlSetData($List1,"Nombre de nombres premiers trouvés dans l'interval : " & $temp)
                    If GUICtrlRead($Checkbox1)=$GUI_CHECKED Then ;sauvegarde
                        FileOpen($file_path,2)
                        FileWrite($file_path,"Recherche des nombres premiers dans l'interval " & "[" & $min & "," & $max &"]" & @CRLF)
                        If $Error=1 Then
                            FileWrite($file_path,"Procedure de calcul interrompue à " & $n & @CRLF)
                        EndIf
                        FileWrite($file_path,"Nombre de nombres premiers trouvés dans l'interval : " & $array[0] & @CRLF)
                        For $i=1 to $temp
                            FileWrite($file_path,$array[$i] & @CRLF)
                        Next
                        FileClose($file_path)
                        MsgBox(0,"","Le fichier a été enregistré")
                    EndIf
                EndIf
            EndIf
    EndSwitch
WEnd

Func Ispremier($n)
    $premier=True
    If Mod($n,2)=0 And $n<>2 Then
        $premier=False
    Else
        $med=Floor($n/2)
        $i=3
        While $i<=$med And $premier=True
            If Mod($n,$i)=0 Then
                $premier=False
            EndIf
            $i=$i+2
        WEnd
    EndIf
    Return $premier
EndFunc
"Ce qui ne tue pas rend plus fort." Nietzsche
Avatar du membre
jchd
AutoIt MVPs (MVP)
AutoIt MVPs (MVP)
Messages : 2272
Enregistré le : lun. 30 mars 2009 22:57
Localisation : Sud-Ouest de la France (43.622788,-1.260864)
Status : Hors ligne

Re: [Ex] Calcul de nombre premiers

#2

Message par jchd »

Ton test de primalité n'est pas optimal, loin de là.
Plutôt que de tester la divisibilité par {3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, ...., n/2} tu devrais déjà faire une étape de "trial divide", testant Mod($n, $p) ?= 0 pour $p IN (2, 3, 5, 7, 11, 13, 17, ...) en te limitant à un ensemble qui flirte avec le point-selle, et surtout, te limiter à Sqrt($n).

Maintenant si l'on souhaite une fonction effiface, pourquoi ne pas utiliser une bibliothèque ad-hoc ?
http://www.autoitscript.com/forum/topic/145763-calculate-big-numbers-using-gmp-dll/#entry1030565
La cryptographie d'aujourd'hui c'est le taquin plus l'électricité.
Avatar du membre
TT22
Membre émérite
Membre émérite
Messages : 1566
Enregistré le : lun. 18 avr. 2011 15:21
Localisation : La Quatrième Dimension
Status : Hors ligne

Re: [Ex] Calcul de nombre premiers

#3

Message par TT22 »

Pas mal, mais il y a du travail avant de dépasser celui-là :lol:
Sinon, il sera bien que le bouton "Lancer" se change en "Arrêter" lors du calcul.

Edit : Et puis pour l'optimisation, étant donné que un nombre premier ne peut pas être pair (à par 2), remplace $n=$n+1 par $n=$n+2 (en s'assurant que $n soit impaire au départ). Cela rendra ton script deux fois plus rapide.

Edit² : Comme ça :
► Afficher le texte
Cordialement,
TT22
Avatar du membre
jchd
AutoIt MVPs (MVP)
AutoIt MVPs (MVP)
Messages : 2272
Enregistré le : lun. 30 mars 2009 22:57
Localisation : Sud-Ouest de la France (43.622788,-1.260864)
Status : Hors ligne

Re: [Ex] Calcul de nombre premiers

#4

Message par jchd »

$n += 2
C'est vrai, je n'ai même pas regardé la boucle principale, ni bien sûr le GUI.

Par contre il ne s'agit pas ici de s'attaquer aux records de factorisation ni de primalité. Pour celà il faut des algorithmes radicalement différents et un matériel hors de portée du seul particulier.
La cryptographie d'aujourd'hui c'est le taquin plus l'électricité.
Avatar du membre
N3mesis
Niveau 2
Niveau 2
Messages : 17
Enregistré le : ven. 01 févr. 2013 11:20
Status : Hors ligne

Re: [Ex] Calcul de nombre premiers

#5

Message par N3mesis »

TT22 a écrit : Edit : Et puis pour l'optimisation, étant donné que un nombre premier ne peut pas être pair (à par 2), remplace $n=$n+1 par $n=$n+2 (en s'assurant que $n soit impaire au départ). Cela rendra ton script deux fois plus rapide.
En fait je l'avais incorporé dans la fonction, mais il est vrai que ça aurait été plus simple et peut etre un peu plus rapide comme ça.
"Ce qui ne tue pas rend plus fort." Nietzsche
Avatar du membre
mikell
Spammer !
Spammer !
Messages : 6292
Enregistré le : dim. 29 mai 2011 17:32
Localisation : Deep Cévennes
Status : Hors ligne

Re: [Ex] Calcul de nombre premiers

#6

Message par mikell »

@TwentyToo
Bien vu le $n=$n+2 mais peut-être comme ça

Code : Tout sélectionner

If _IsPair(Ceiling($min)) Then $min += 1
$n=$min
While $n<=$max
....

; remplacé par :
$min += 1 - Mod($min, 2)
For $i = $min to $max step 2
....
avec un petit moteur regex

Code : Tout sélectionner

Func _Ispremier($n)
 Local $s
 For $j = 1 To $n
     $s &= "a"
 Next
 ; ze regex is from jchd
 If not StringRegExp($s, '^a$|^(aa+)\1+$') Then Return true
 Return false
EndFunc
" L'échec est le fondement de la réussite. " (Lao-Tseu )
" Plus ça rate, plus on a de chances que ça marche " (les Shadoks )
Avatar du membre
jchd
AutoIt MVPs (MVP)
AutoIt MVPs (MVP)
Messages : 2272
Enregistré le : lun. 30 mars 2009 22:57
Localisation : Sud-Ouest de la France (43.622788,-1.260864)
Status : Hors ligne

Re: [Ex] Calcul de nombre premiers

#7

Message par jchd »

Elle n'est pas de moi et remonte à des lunes.
Bon, faut pas lancer ça sur un nombre de 14 chiffres, hein ! Si on veut une fonction utilisable en général sur nos entiers de 63 bits, mieux vaut implémenter un test Miller-Rabin en C dans une DLL minuscule, ou s'appuyer sur GMP comme je suggérais.
La cryptographie d'aujourd'hui c'est le taquin plus l'électricité.
Répondre