Décomposition d’un nombre en produit de facteurs premiers

Vous débutez et vous avez besoin d'aide ? N'hésitez pas à poser vos questions
PAPIPP
Messages : 534
Inscription : sam. 23/févr./2008 17:58

Décomposition d’un nombre en produit de facteurs premiers

Message par PAPIPP »

Bonjour à tous.


Voici un Algo par divisions successives pour une décomposition d’un nombre en produit de facteurs premiers.
Le nombre 1 n'est pas par convention un nombre premier. Je l'ai placé malgré cela dans le produit de facteur. Vous pouvez le retirer.

Par ailleurs pour accélérer le processus à partir du diviseur 3 j’ai placé un pas de 2. Ainsi les diviseurs ne seront plus que des nombre impairs 3 5 7 9 11 13 15 etc..Ceci permet de diviser le temps par plus de 2

Attention?
Vous pouvez tester avec ce nombre 9223372036854675807
9223372036854675807=3*4324027*711017148047 avec un temps sur ma machine de 106,687 secondes
Alors que
9223372036854775807=7*7*73*127*337*92737*649657 avec un temps sur ma machine de 0,154 seconde
On peut en déduire qu’on ne sait ni le nombre de facteurs ni le temps que le processus va mettre.

Cet algo peut prendre un temps extrêmement important sur les nombres très grands de Mersen Mn=2^n-1 ou mieux sur les nombres très grands de Fermat Fn= 2^(2^n)+1 ou sur les très grands nombres premiers

Les nombres de Mersenne sont de la forme Mn=2^n-1
M1=2^1-1=1
M2=2^2-1=3
M3=2^3-1=7
M4=2^4-1=15
M5=2^5-1=31
M7=2^7-1=127
Propriétés des nombres de Mersenne
Si n n'est pas premier alors 2^n – 1 n'est pas premier.
Mais M11=2^11-1=2047=23*89 n’est pas premier

Seules les 5 premiers nombres de Fermat sont premiers Il est difficile de contrôler les autres nombre car ils augmentent très rapidement
Voici le 6 premiers nombres de Fermat Fn= 2^(2^n)+1
F0=2^(2^0)+1=3
F1=2^(2^1)+1=5
F2=2^(2^2)+1=17
F3=2^(2^3)+1=257
F4=2^(2^4)+1=65537
F5=2^(2^5)+1= 4294967297 celui-ci n’est pas premier = 641*6700417
Avant le 3 février 2010, le plus petit nombre de Fermat composé dont on ne connaissait aucun diviseur premier était F14. Le 3 février 2010, un facteur premier de F14 a été découvert par Tapio Rajala, Département de Mathématiques et Statistiques, Université de Jyväskylä, Finlande. Voir le site prothsearch . Tapio Rajala a annoncé sur le mersenneforum que F14 est divisible par 116928085873074369829035993834596371340386703423373313.

Comme ces nombres très grands n'ont pas beaucoup de facteurs premiers, ils prennent beaucoup de temps machine c’est pourquoi d’autres algo ont été trouvés.
S’il est facile d' obtenir le produit de deux grands nombres premiers donnés. Par contre, il est beaucoup plus difficile de trouver les facteurs premiers de celui-ci. C'est ce que l'on appelle une fonction trappe. Ceci s'applique pour les systèmes modernes en cryptologie (l'algorithme à clé publique RSA)

Voici à titre de document les différents algo de décomposition (je ne les connais pas tous).

Le temps d'exécution des algorithmes de factorisation à but général dépend de la taille de l'entier à factoriser et des facteurs qui le composent. Ceci est le type d'algorithme utilisé pour factoriser les nombres RSA. La plupart des algorithmes de factorisation à but général sont basés sur la méthode des congruence de carrés.

- Divisions successives
- Algorithme rho de Pollard
- Algorithme p-1 de Pollard
- Factorisation en courbe elliptique de Lenstra
- Congruence de carrés (Méthode de factorisation de Fermat)
- Crible spécial de corps de nombres (SNFS)
- Crible quadratique
- Crible général de corps de nombres (GNFS)

Code : Tout sélectionner

; algorithme de DECOMPOSITION EN FACTEURS_PREMIERS
; Le nombre 1 n'est pas par convention un nombre premier.
; Je l'ai placé malgré cela dans le produit de facteur. Vous pouvez le retirer
EnableExplicit
Define nb$,nb.q,l2nb.d,nbl2.q,nbMAX.q,NBREC.q,P.q,i,pas,fact_prem$,j,deb.q,mess$

saisie:
mess$+"Décomposition en facteur premier"
If Len(mess$)>99
  MessageRequester("Erreur","Donnez un entier positif < ou  9223372036854775807"+#CR$+"Relancez le prg")
  End
EndIf  
nb$=InputRequester(mess$,"Donnez un entier positif < ou = 9223372036854775807","9223372036854775807") ; c'est la limite d'un type q
If Len(nb$)>Len("9223372036854775807") 
  Goto saisie
EndIf
nb.q=Val(nb$)
If nb<1
  Goto saisie
EndIf  
; si le nombre nb est   pair il peut être une puissance de 2 nb=2^n avec n positions max dans la table donc n=log2(nb)
; si le nombre nb est impair il peut être une puissance de 3 nb=3^n avec n positions max dans la table donc n=log3(nb)
If nb%2=0
  l2nb.d=Log(nb)/Log(2)
Else
  l2nb.d=Log(nb)/Log(3)
EndIf
nbl2.q=l2nb          ; conversion en nb entier
NBMAX.Q=Sqr(NB)      ;limite de recherche des facteurs premiers
NBREC.Q=1
Dim Tab.q(NBl2)
p=2
i=0
pas=1
fact_prem$=nb$+"="
deb.q=ElapsedMilliseconds()
While (p<=NBMAX) And (nb>1)
  If nb%p=0
    tab(i)=p
    nb=nb/p
    i+1
  Else
    p+pas
  EndIf
  ; ********** les 3 instructions suivantes accélèrent le processus sur les grands nombres  (pas de 2 à partir du diviseur 3 on ne garde que les diviseurs impairs )
  If p=3
    pas=2
  EndIf
Wend
tab(i)=nb
If tab(i)<>1
  I+1
  tab(i)=1
EndIf
For j=0 To i
  fact_prem$+tab(j)
  NBREC*tab(j) ; Vérification de la décomposition
  If j<i
    fact_prem$+"*"
  EndIf
Next
MessageRequester("Résultat",fact_prem$+#CR$+Str(NBREC)+": contrôle"+#CR$+"temps="+Str(ElapsedMilliseconds()-deb)+"ms"+#CR$+"Nb postions de la table :"+Str(nbl2))
A+
Dernière modification par PAPIPP le mar. 09/déc./2014 21:52, modifié 4 fois.
Il est fort peu probable que les mêmes causes ne produisent pas les mêmes effets.(Einstein)
Et en logique positive cela donne.
Il est très fortement probable que les mêmes causes produisent les mêmes effets.
Avatar de l’utilisateur
Fig
Messages : 1176
Inscription : jeu. 14/oct./2004 19:48

Re: Décomposition d’un nombre en produit de facteurs premier

Message par Fig »

Vraiment du bon boulot !! :D

Je pense que tu as fait le plus dur... Maintenant la Nsa va être à tes basques ! :mrgreen:

En réagençant un peu je gagne 18-20% sur mon pc... Mais c'ets beaucoup moins beau que ce que tu as fait. Image

Code : Tout sélectionner

Repeat
  If nb%p=0
    tab(i)=p
    nb=nb/p
    i+1
    If nb<=1:Break:EndIf
  Else
    p+pas
    If p=3 Or p>NBMAX:Break:EndIf
  EndIf
ForEver
pas=2
Repeat
  If nb%p=0
    tab(i)=p
    nb=nb/p
    i+1
    If nb<=1:Break:EndIf
  Else
  p+pas
  If p>NBMAX:Break:EndIf
  EndIf  
ForEver
Il y a deux méthodes pour écrire des programmes sans erreurs. Mais il n’y a que la troisième qui marche.
Version de PB : 6.00LTS - 64 bits
Avatar de l’utilisateur
Kwai chang caine
Messages : 6989
Inscription : sam. 23/sept./2006 18:32
Localisation : Isere

Re: Décomposition d’un nombre en produit de facteurs premier

Message par Kwai chang caine »

Comme tout ce qui me dépasse, je trouve ça beau 8O
Il y a donc un nombre incalculable de choses belles à mes yeux :mrgreen:
Merci du partage de ton savoir 8)
Il parait que ça se transmet...c'est juste dommage que ce dernier ne s'attrape pas aussi facilement que la petite vérole :|
ImageLe bonheur est une route...
Pas une destination

PureBasic Forum Officiel - Site PureBasic
Avatar de l’utilisateur
kernadec
Messages : 1606
Inscription : ven. 25/avr./2008 11:14

Re: Décomposition d’un nombre en produit de facteurs premier

Message par kernadec »

bonsoir PAPIPP
ça envoie du steak :D merci pour le partage

Cordialement
PAPIPP
Messages : 534
Inscription : sam. 23/févr./2008 17:58

Re: Décomposition d’un nombre en produit de facteurs premier

Message par PAPIPP »

Merci à tous
à Fig
C'est très bien de faire 2 boucles l'une avec un pas =1 et l'autre avec un pas =2
cela évite sur les très grands nombres de tester à chaque itération si le diviseur p =3
le gain est proche de18 à 20% c'est pas mal.
Merci.
Il est fort peu probable que les mêmes causes ne produisent pas les mêmes effets.(Einstein)
Et en logique positive cela donne.
Il est très fortement probable que les mêmes causes produisent les mêmes effets.
Avatar de l’utilisateur
Fig
Messages : 1176
Inscription : jeu. 14/oct./2004 19:48

Re: Décomposition d’un nombre en produit de facteurs premier

Message par Fig »

:lol: Oui je sais bien que c'est ridicule au vu de ton travail de recherche.... Encore bravo.
Il y a deux méthodes pour écrire des programmes sans erreurs. Mais il n’y a que la troisième qui marche.
Version de PB : 6.00LTS - 64 bits
PAPIPP
Messages : 534
Inscription : sam. 23/févr./2008 17:58

Re: Décomposition d’un nombre en produit de facteurs premier

Message par PAPIPP »

Bonjour à tous.

Voici la dernière optimisation du code avec une MACRO.

Code : Tout sélectionner

; algorithme de DECOMPOSITION EN FACTEURS_PREMIERS
; Le nombre 1 n'est pas par convention un nombre premier.
; Je l'ai placé malgré cela dans le produit de facteur. Vous pouvez le retirer
EnableExplicit
Define nb$,nb.q,l2nb.d,nbl2.q,nbMAX.q,NBREC.q,DIV.q,i,pas,fact_prem$,j,deb.q,mess$
Macro decompose(Test_)
  Repeat
    If nb%DIV=0
      tab(i)=DIV
      nb/DIV
      i+1
      If nb<=1:Break:EndIf
    Else
      DIV+pas
      If Test_:Break:EndIf
    EndIf
  ForEver
EndMacro

saisie:
mess$+"Décomposition en facteur premier"
If Len(mess$)>99
  MessageRequester("Erreur","Donnez un entier positif < ou  9223372036854775807"+#CR$+"Relancez le prg") ;
  End
EndIf
nb$=InputRequester(mess$,"Donnez un entier positif < ou = 9223372036854775807","9223372036854775807") ; c'est la limite d'un type q  2^63-1 
;;                                                                                   en puissance de 2=>2^62 donne le plus grand nombre de facteurs 
If Len(nb$)>Len("9223372036854775807")                                         ;; en puissance de 3 => 3^39
  Goto saisie
EndIf
nb.q=Val(nb$)
If nb<1
  Goto saisie
EndIf
; si le nombre nb est   pair il peut être une puissance de 2 nb=2^n avec n positions max dans la table donc n=log2(nb)
; si le nombre nb est impair il peut être une puissance de 3 nb=3^n avec n positions max dans la table donc n=log3(nb)
If nb%2=0
  l2nb.d=Log(nb)/Log(2)
Else
  l2nb.d=Log(nb)/Log(3)
EndIf
nbl2.q=l2nb          ; conversion en nb entier
NBMAX.Q=Sqr(NB)      ;limite de recherche des facteurs premiers
NBREC.Q=1
Dim Tab.q(NBl2)
DIV=2
i=0
pas=1
fact_prem$=nb$+"="
deb.q=ElapsedMilliseconds()
decompose(DIV=3)
;; (pas de 2 à partir du diviseur 3 on ne garde que les diviseurs impairs)
pas=2
decompose(DIV>NBMAX)
tab(i)=nb
If tab(i)<>1
  I+1
  tab(i)=1
EndIf
For j=0 To i
  fact_prem$+tab(j)
  NBREC*tab(j) ; Vérification de la décomposition
  If j<i
    fact_prem$+"*"
  EndIf
Next
MessageRequester("Résultat",fact_prem$+#CR$+Str(NBREC)+": contrôle"+#CR$+"temps="+Str(ElapsedMilliseconds()-deb)+"ms"+#CR$+"Nb postions de la table :"+Str(nbl2))

Il est fort peu probable que les mêmes causes ne produisent pas les mêmes effets.(Einstein)
Et en logique positive cela donne.
Il est très fortement probable que les mêmes causes produisent les mêmes effets.
PAPIPP
Messages : 534
Inscription : sam. 23/févr./2008 17:58

Re: Décomposition d’un nombre en produit de facteurs premier

Message par PAPIPP »

Bonjour à tous.

Comme il est inutile de balayer au-delà de la racine carrée du nombre restant à analyser
Voici un dernier essai nettement plus rapide que les précédents.

Code : Tout sélectionner

; algorithme de DECOMPOSITION EN FACTEURS_PREMIERS
; Le nombre 1 n'est pas par convention un nombre premier.
; Je l'ai placé malgré cela dans le produit de facteur. Vous pouvez le retirer
EnableExplicit
Define nb$,nb.q,l2nb.d,nbl2.q,nbMAX.q,NBREC.q,DIV.q,i,pas,fact_prem$,j,deb.q,mess$
Macro decompose(Test_)
  Repeat
    If nb%DIV=0
      tab(i)=DIV
      nb/DIV
      i+1
      nbmax=Sqr(nb)
      If div>nbmax : Break: EndIf
      If nb<=1:Break:EndIf
    Else
      DIV+pas
      If Test_:Break:EndIf
    EndIf
  ForEver
EndMacro

saisie:
mess$+"Décomposition en facteur premier"
If Len(mess$)>99
  MessageRequester("Erreur","Donnez un entier positif < ou  9223372036854775807"+#CR$+"Relancez le prg") ;
  End
EndIf
nb$=InputRequester(mess$,"Donnez un entier positif < ou = 9223372036854775807","9223372036854775807") ; c'est la limite d'un type q  2^63-1
;;                                                                                   en puissance de 2=>2^62 donne le plus grand nombre de facteurs
If Len(nb$)>Len("9223372036854775807")                                         ;; en puissance de 3 => 3^39
  Goto saisie
EndIf
nb.q=Val(nb$)
If nb<1
  Goto saisie
EndIf
; si le nombre nb est   pair il peut être une puissance de 2 nb=2^n avec n positions max dans la table donc n=log2(nb)
; si le nombre nb est impair il peut être une puissance de 3 nb=3^n avec n positions max dans la table donc n=log3(nb)
If nb%2=0
  l2nb.d=Log(nb)/Log(2)
Else
  l2nb.d=Log(nb)/Log(3)
EndIf
nbl2.q=l2nb          ; conversion en nb entier
NBMAX.Q=Sqr(NB)      ;limite de recherche des facteurs premiers
NBREC.Q=1
Dim Tab.q(NBl2)
DIV=2
i=0
pas=1
fact_prem$=nb$+"="
deb.q=ElapsedMilliseconds()
decompose(DIV=3)
;; (pas de 2 à partir du diviseur 3 on ne garde que les diviseurs impairs)
pas=2
decompose(DIV>NBMAX)
tab(i)=nb
If tab(i)<>1
  I+1
  tab(i)=1
EndIf
For j=0 To i
  fact_prem$+tab(j)
  NBREC*tab(j) ; Vérification de la décomposition
  If j<i
    fact_prem$+"*"
  EndIf
Next
MessageRequester("Résultat",fact_prem$+#CR$+Str(NBREC)+": contrôle"+#CR$+"temps="+Str(ElapsedMilliseconds()-deb)+"ms"+#CR$+"Nb postions de la table :"+Str(nbl2))
A+
Il est fort peu probable que les mêmes causes ne produisent pas les mêmes effets.(Einstein)
Et en logique positive cela donne.
Il est très fortement probable que les mêmes causes produisent les mêmes effets.
Avatar de l’utilisateur
Kwai chang caine
Messages : 6989
Inscription : sam. 23/sept./2006 18:32
Localisation : Isere

Re: Décomposition d’un nombre en produit de facteurs premier

Message par Kwai chang caine »

32 ms avec ma charette pour 9223372036854775807 c'est fast and very furious 8O
Merci PAPIPP 8)
ImageLe bonheur est une route...
Pas une destination

PureBasic Forum Officiel - Site PureBasic
PAPIPP
Messages : 534
Inscription : sam. 23/févr./2008 17:58

Re: Décomposition d’un nombre en produit de facteurs premier

Message par PAPIPP »

Bonjour à tous

Voici la fin de l’optimisation de la décomposition d’un nombre en facteur premier
Suivant l’ago des divisions successives des nombre premiers inférieures à la racine carré du nombre restant à décomposer. L’optimisation ici est la programmation en FASM dans la macro.

Pour accélérer encore cet algo il faut réduire le nombre de divisions à effectuer.
1) Première méthode, n’utiliser que les nombres premiers inférieures à la racine carré du nombre restant à décomposer
2) la première méthode implique que nous connaissions les nombres premiers inférieures à la racine carré du nombre
restant à décomposer. Cela n’est pas évident sur les très grands nombres.
Il nous faut soit trouver une méthode qui détermine à partir de N le N+1 prochain nombre premier ou avoir un
crible qui ne laisse échapper ou passer aucun nombre premier

C’est cette dernière méthode que je suis en train de tester avec un crible +2 suivi de +4 a partir du diviseur 5 on a donc à partir de 5
5 +2 =7
7+4=11
11+2=13
13+4=17
17+2=19
19+4=23 …..etc
On voit sur ces quelques essais qu’aucun nb premier n’a échappé Mais je n’ai aucune démonstration mathématique me prouvant que cela est vrai pour tous les nombres générés par cette méthode.
Par contre il restera encore des diviseurs inutiles qui augmentent le temps de l’algo.
Avec cette méthode on réduit le temps de 1/3 (2 divisions à la place de 3)

Vous pouvez tester cette méthode en décommentant les 7 lignes définies dans le prg.

Code : Tout sélectionner

; algorithme de DECOMPOSITION EN FACTEURS_PREMIERS
; Le nombre 1 n'est pas par convention un nombre premier.
; Je l'ai placé malgré cela dans le produit de facteur. Vous pouvez le retirer
EnableExplicit
Define nb$,nb.q,l2nb.d,nbl2.q,nbMAX.q,NBREC.q,DIV.l,i,pas,fact_prem$,j,deb.q,mess$,quotient.q,reste.l,quotientp.q,*Tab,ind.l
Macro decompose(Test_)
  Repeat
    ;     ;Le nom de @@: signifie étiquette anonyme,vous pouvez avoir défini un grand nombre d'entre eux dans la source.
    ;     ;Symbole @b(ou l'équivalent @r)le plus proche des références du label précédent anonyme
    ;     ;,symbole @f références plus proche de l'étiquette suivante anonyme.
    ;     ;Ces symboles spéciaux sont insensibles à la casse.
    ;;*******************************  TESTS EN ASM ********************************************************************
    ;*************************************** Division d'un nombre de 64 bits par un nombre de 32 bits ******************************************
    EnableASM
    MOV ecx,dword[v_DIV]
    XOr EDX,EDX
    MOV eax,dword[v_nb+4]
    DIV ecx
    MOV dword[v_quotientp],eax
    MOV eax,dword[v_nb]
    DIV ecx
    CMP edx,0
    JNZ @f
    ;     MOV dword[v_reste],edx
    MOV edx,dword[v_quotientp]
    mov dword[v_nb+4],edx
    MOV dword[v_nb],eax
    ;************************************************ Recherche de la racine carré ***************************************************************
    FILD qword[v_nb]
    FSQRT
    ; !FISTTP dword [v_nbMAX] ; avec arrondi si vous décommentez cette instruction commentez la précédente
    ;                           et laissez le ! car l'instruction FISTTP n'est pas reconnue par PureBasic avec !FISTTP c'est bon !!!!
    FISTP dword[v_nbMAX] ; sans arrondi
    ;*********************************************** Affectation de la valeur du DIViseur dans la table *******************************************
    ;     MOV ecx, [v_DIV]; à decommenter si ecx est effacée
    mov ebx, [p_Tab]
    mov edx, [v_ind]
    add ebx,edx
    mov[ebx],ecx
    add edx,8
    mov[v_ind],edx
  DisableASM
    If nb<=1:Break:EndIf
    EnableASM
    JMP lab#MacroExpandedCount
    !@@:
     mov edx,[v_pas]
     ADD [v_DIV],edx
     DisableASM
  ;********************************************************************************************************************************************************
  ;********************************************************************************************************************************************************
; ;      ; ; pour accélérer on gagne presque 1/3  du temps avec un saut a 4 au lieu de 2 1 fois sur 2 aucune explication pour justifier cet algo div>5 !!!
; ;      ; j'ai testé jusqu'au nombre 1223 et cette méthode est bonne  mais ne peut-il pas avoir un nombre premier qui échappe à ce crible ???
; ;***********************************  Pour accélerer encore l' algo vous pouvez décommentez les 7 lignes PB suivantes *******************************
;       If div>5 And  pas>1
;          If pas>2 
;            pas=2
;          Else
;            pas=4
;          EndIf 
;      EndIf
     ;************************************  Pour accélerer encore l' algo vous pouvez décommentez les 7 lignes PB précedentes ******************************
    ;*******************************************************************************************************************************************************
    
    If Test_:Break:EndIf
    !lab#MacroExpandedCount:
  ForEver
  !FIN#MacroExpandedCount:
EndMacro

saisie:
mess$+"Décomposition en facteur premier"
If Len(mess$)>99
  MessageRequester("Erreur","Donnez un entier positif < ou  9223372036854775807"+#CR$+"Relancez le prg") ;
  End
EndIf
nb$=InputRequester(mess$,"Donnez un entier positif < ou = 9223372036854775807","9223372036854775807") ; c'est la limite d'un type q  2^63-1
;;                                                                                   en puissance de 2=>2^62 donne le plus grand nombre de facteurs
If Len(nb$)>Len("9223372036854775807")                                         ;; en puissance de 3 => 3^39
  Goto saisie
EndIf
nb.q=Val(nb$)
If nb<1
  Goto saisie
EndIf
; si le nombre nb est   pair il peut être une puissance de 2 nb=2^n avec n positions max dans la table donc n=log2(nb)
; si le nombre nb est impair il peut être une puissance de 3 nb=3^n avec n positions max dans la table donc n=log3(nb)
If nb%2=0
  l2nb.d=Log(nb)/Log(2)
Else
  l2nb.d=Log(nb)/Log(3)
EndIf
nbl2.q=l2nb          ; conversion en nb entier
NBMAX.Q=Sqr(NB)      ;limite de recherche des facteurs premiers
NBREC.Q=1
Dim Tab.q(NBl2)
*Tab=@Tab()
DIV=2
i=0
pas=1
fact_prem$=nb$+"="
deb.q=ElapsedMilliseconds()
decompose(DIV=3)
;; (pas de 2 à partir du diviseur 3 on ne garde que les diviseurs impairs)
pas=2
decompose(DIV>NBMAX)
i=ind/8
tab(i)=nb
If tab(i)<>1
  I+1
  tab(i)=1
EndIf
For j=0 To i
  fact_prem$+tab(j)
  NBREC*tab(j) ; Vérification de la décomposition
  If j<i
    fact_prem$+"*"
  EndIf
Next
MessageRequester("Résultat",fact_prem$+#CR$+Str(NBREC)+": contrôle"+#CR$+"temps="+Str(ElapsedMilliseconds()-deb)+"ms"+#CR$+"Nb postions de la table :"+Str(nbl2))
A+
Il est fort peu probable que les mêmes causes ne produisent pas les mêmes effets.(Einstein)
Et en logique positive cela donne.
Il est très fortement probable que les mêmes causes produisent les mêmes effets.
PAPIPP
Messages : 534
Inscription : sam. 23/févr./2008 17:58

Re: Décomposition d’un nombre en produit de facteurs premier

Message par PAPIPP »

Bonjour à tous.
Avant de poursuivre il nous faut un peu de théorie.
Voici la méthode que j'ai utilisée et son explication pour optimiser la recherche de décomposition d’un nombre en facteur premier.

Le principe est de diminuer le nombre des divisions inutiles. Il faut donc diminuer le nombre de diviseurs qui ne seront certainement pas premiers.
1) Dans un premier temps on prend tous les diviseurs du premier nombre premier (2) jusqu’à la racine carré du nombre restant à décomposer.
2) Dans un deuxième temps on voit que tous les nombre pairs ne peuvent être premiers hors mis 2 il faut donc les supprimer.
Voici la méthode utilisée qui pourra être généralisée.

En mathématiques et en programmation informatique, on désigne par modulo l’opération de calcul du reste de la division euclidienne.
Pour faire apparaitre tous les nombre ayant le même reste dans une division euclidienne en modulo x ici x sera 2
La meilleure méthode pour faire apparaitre les mêmes restes est de dresser un tableau dans lequel les mêmes restes sont dans la même colonne.
J'ai disposé les nombres de 1 à 29 mais on peut continuer suivant un modulo 2.
Les nombres de la colonne (3) ici ou sur fond bleu sont soit des nombres premiers soit des multiples de nombre premier 3 ou des nb premiers >3 comme par exemple 5*7=35 qui serait dans la colonne 3
La colonne 2 ne contient que des multiples de 2
Donc en éliminant tous les nombres de la colonne 2 à l’exception de 2 lui-même puisque c’est un nombre premier, on élimine la moitie des Diviseurs à essayer

Code : Tout sélectionner

1	02	03	
	04	05	
	06	07	
	08	09	
	10	11	
	12	13	
	14	15	
	16	17	
	18	19	
	20	21	
	22	23	
	24	25	
	26	27	
	28	29	
Différence +2
Différence pour retrouver le prochain nombre susceptible d’être premier 3+2 =5 ou 5+2=7 etc..
En modulo 2 la colonne 3 et la colonne 1 ont le même reste de la division euclidienne mais cette représentation est un artifice de programmation.

Maintenant avec cette méthode essayons de supprimer les multiples de 2 mais aussi de 3
Ce qui nous donne un modulo = 2*3=6 donc 6 colonnes mais comme la première avec 1 et la dernière on le même reste nous aurons 2*3+1= 7 colonnes
Ayant disposé les nombres de 1 à 109 mais on peut continuer suivant un modulo 2*3=6
Toute les zones sur fond bleu sont soit des nombres premiers soit des multiples de nombre premier encore inconnu c'est-à-dire ni multiple de 2 ni multiple de 3
La colonne 2 ne contient que des multiples de 2 la colonne 3 des multiples de 3 la colonne 4 des multiples de 2 et la colonne 6 des multiples de 2 et de 3
On voit qu’à partir d’un nombre appartenant à la première colonne bleu par exemple on peut trouver tous les nombres des 2 colonnes en ajoutant +2 pour le prochain nombre de la deuxième colonne bleu et ensuite + 4 pour obtenir le deuxième nombre de la première colonne.
Donc à partir de 5 on peut appliquer +2 suivi de +4 pour générer la colonne 5 et la colonne 7
Qui contiennent toutes le 2 tous les nombres premiers mais aussi des multiples de 5 et de 7
ou des multiples de nombres premiers encore inconnus c'est-à-dire différent de 2,3,5,7
On a ainsi gagné 1/3 de temps sur les nombres impairs puisqu’on élimine la colonne 3 donc un rapport de 3 colonnes de Nb impaires et ici 2 colonnes à exploiter

REMARQUES :
On peut avec cette méthode trouver aussi les nombres premiers.
Si vous voulez connaître les nombre premiers entre 2 bornes Nmin et Nmax il devient possible en modulo 6 d’obtenir la colonne d’appartenance et ainsi de trouver le premier nombre appartenant à la colonne 5 ou 7 le plus proche si l’on pas obtenu comme reste 5 ou 7
Ensuite il suffit de continuer en + 2 ou + 4 suivant l’appartenance à la colonne et de continuer en alternant + 2 et + 4 jusqu’à Nmax en testant tous les nombres trouvés par cette méthode par tous les nombre premiers inférieurs ou égaux à la racine carré de Nmax .

Image

Code : Tout sélectionner

1	2	3	4	5	6	7	
	8	9	10	11	12	13	
	14	15	16	17	18	19	
	20	21	22	23	24	25	
	26	27	28	29	30	31	
	32	33	34	35	36	37	
	38	39	40	41	42	43	
	44	45	46	47	48	49	
	50	51	52	53	54	55	
	56	57	58	59	60	61	
	62	63	64	65	66	67	
	68	69	70	71	72	73	
	74	75	76	77	78	79	
	80	81	82	83	84	85	
	86	87	88	89	90	91	
	92	93	94	95	96	97	
	98	99	100	101	102	103	
	104	105	106	107	108	109	

Code : Tout sélectionner

Différence entre colonnes	(5 et 7)	2		4  qui comportent des nombres premiers.
Donc on ne peut trouver des nombres premiers que dans les colonnes 5 et 7 avec comme premier diviseur 5  avec la suite modulo 6= 2+4 



 
Maintenant nous pouvons supprimer les multiples de 2 , 3 et 5 
Pour améliorer encore et diminuer le nombre de diviseur on peut disposer les nombres suivant le modulo 2*3*5 =30 toujours à partir de 2

1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25	26	27	28	29	30	31	
	32	33	34	35	36	37	38	39	40	41	42	43	44	45	46	47	48	49	50	51	52	53	54	55	56	57	58	59	60	61	
	62	63	64	65	66	67	68	69	70	71	72	73	74	75	76	77	78	79	80	81	82	83	84	85	86	87	88	89	90	91	
	92	93	94	95	96	97	98	99	100	101	102	103	104	105	106	107	108	109	110	111	112	113	114	115	116	117	118	119	120	121	
	122	123	124	125	126	127	128	129	130	131	132	133	134	135	136	137	138	139	140	141	142	143	144	145	146	147	148	149	150	151	
	152	153	154	155	156	157	158	159	160	161	162	163	164	165	166	167	168	169	170	171	172	173	174	175	176	177	178	179	180	181	
	182	183	184	185	186	187	188	189	190	191	192	193	194	195	196	197	198	199	200	201	202	203	204	205	206	207	208	209	210	211	
	212	213	214	215	216	217	218	219	220	221	222	223	224	225	226	227	228	229	230	231	232	233	234	235	236	237	238	239	240	241	
	242	243	244	245	246	247	248	249	250	251	252	253	254	255	256	257	258	259	260	261	262	263	264	265	266	267	268	269	270	271	
	272	273	274	275	276	277	278	279	280	281	282	283	284	285	286	287	288	289	290	291	292	293	294	295	296	297	298	299	300	301	
	302	303	304	305	306	307	308	309	310	311	312	313	314	315	316	317	318	319	320	321	322	323	324	325	326	327	328	329	330	331	
Différence entre colonnes 4 2 4 2 4 6 2 6



Les colonnes 2 4 6 8 10 12 14 16 18 20 22 24 26 28 30 sont divisible par 2 il ne peut y avoir de nombre premier dans ces colonnes
Les colonnes 3 5 9 15 21 25 27 sont divisibles par 3 ou 5 donc il ne peut y avoir de nombre premier dans ces colonnes
Donc on ne peut trouver des nombres premiers que dans les colonnes 7,11,13,17,19,23,29,31 avec comme premier diviseur 7 avant la suite modulo 30 => 4 2 4 2 4 6 2 6 avec pour somme 30
Ici le gain sera de 15/15-8/15= 7/15 de 47%
Généralisons cette méthode
Mais tout d’abord vérifions la théorie.(le terme modulo est le reste de la division euclidienne)
Soit N le premier Nb premier avant la répétition en modulo et Nb le nombre dont on veut connaitre les caractéristiques

1) déterminons le modulo exemple premier nb avant application du vecteur modulo (5) => 2*3*5=30
2) Déterminons maintenant à quelle colonne le 2<=Nbc<=Nb est affecté
Nbc=N° de colonne=(Nb-1 modulo 30)+1 ou encore (Nb-1%30)+1
En plaçant les nombres suivant cette convention on sait que chaque colonne peut être un multiple de 2 , 3 ou 5 et que celle qui ne le sont pas sont des colonnes ou l’on peut trouver des nouveaux nombres premiers ou des multiple de nb premier >à 5
3) déterminons les colonnes qui ne sont pas multiples de 2 , 3 ou 5
les colonnes où l’on trouve des Nb premiers sont les colonnes dont les nombres modulo 30 ne sont pas multiple de 2 , 3 ,ou 5
Ce sont les colonnes 7 11 13 17 19 23 29 31 dont les têtes des colonnes (7 11 13 17 19 23) sont premiers puisque < à 7*7=49

Pour continuer sur ce principe on peut éliminer les multiples des nombres premiers 2 3 5 7.
On peut ainsi continuer pour éliminer la colonne 7 en plaçant les nombres suivant un modulo 2*3*5*7=210.
On élimine ainsi tous les multiples de 2 3 5 et 7 avec un modulo de 210.

On peut continuer ainsi en éliminant les multiples de 2 3 5 7 et 11 avec un modulo de 2*3*5*7*11=2310.

Voici un prg qui tient compte de ces remarques vous pouvez choisir un nombre premier max qui permet d’éliminer tous les multiples des nb premiers <= à max.
J'ai limité la possibilité de choisir entre 2 3 5 7 et 11 car le modulo pour éliminer tous les multiples <= à 11 est égale 2*3*5*7*11=2310 qui est aussi le nombre d"éléments du vecteur à l'origine et j'ai limité la table du prg à 3000 éléments

Code : Tout sélectionner

; algorithme de DECOMPOSITION EN FACTEURS_PREMIERS
; Le nombre 1 n'est pas par convention un nombre premier.
; Je l'ai placé malgré cela dans le produit de facteur. Vous pouvez le retirer
EnableExplicit
DisableDebugger
Structure DIV
	PREMDIV.l
	NBSEQ.l
	Array TDIF.l(3000);; Dimension liée aux nombre d'éléments du vecteur pour 11 il ya 2310 éléments
EndStructure
Global nbs.l,NBSEQ.l
Procedure choixdiv(*EL.DIV)
	Protected mess$,nb$,ELEM,ipas,i
	;********************************************* Choix du filtre à tester *********************************
	nbs=7
	;   Goto FINSAISIE0 ;;;; si vous ne désirez plus choisir les multiples des nb premiers à éliminer commentez cette ligne et imposer nbs juste au dessus
	SAISIE0:
	mess$+"Filtre de réduction des diviseurs"
	If Len(mess$)>120
		MessageRequester("Erreur","Eliminer les multiples des nb premiers <= à  2 3 5 7 11"+#CR$+"Relancez le prg") ;
		End
	EndIf
	nb$=InputRequester(mess$,"Eliminer les multiples des nb premiers <= à 2 3 5 7 11","7") ;
	If Len(nb$)>Len("11")
		Goto SAISIE0
	EndIf
	nbs=Val(nb$)
	If nbs<1 Or nbs>11
		Goto SAISIE0
	EndIf
	FINSAISIE0:
	; ***************************  Chargement de la séquence à tester ******************************
	Select nbs
		Case 1,2
			Restore DIV_2
		Case 3,4
			Restore DIV_3
		Case 5,6
			Restore DIV_5
		Case 7 To 9
			Restore DIV_7
		Case 10 To 11
			Restore DIV_11
			
	EndSelect
	Read.l *EL\PREMDIV
	i=0
	Repeat
		Read.l ELEM
		If ELEM<>0
			*EL\TDIF(I)=elem
			i+1
		EndIf
	Until ELEM=0
	*EL\NBSEQ=I
	nbseq=I
		ipas=0
		DataSection
			DIV_2:;;;***** 3 est le premier diviseur auquel la séquence s'applique Simple élimination des nombres pairs
			Data.l 3,2,0;
			DIV_3:;;***** 5 est le premier diviseur auquel la séquence s'applique pour 2*3=6 gain de 30% environ élimination des multiples 2 3
			Data.l 5,2,4,0;
			DIV_5:; ***** 7 est le premier diviseur auquel la séquence s'applique pour 2*3*5=30, élimination des multiples 2 3 5
			Data.l 7,4,2,4,2,4,6,2,6,0
			DIV_7: ;;*****  11 est le premier diviseur auquel la séquence s'applique pour 2*3*5*7=210, élimination des multiples de 2 3 5 7
			Data.l 11,2,4,2,4,6,2,6,4,2,4,6,6,2,6,4,2,6,4,6,8,4,2,4,2,4,8,6,4,6,2,4,6,2,6,6,4,2,4,6,2,6,4,2,4,2,10,2,10,0
			DIV_11: ;;**** 13 est le premier diviseur auquel la séquence s'applique pour 2*3*5*7*11=2310, élimination des multiples de 2 3 5 7 11
			Data.L 13,4,2,4,6,2,6,4,2,4,6,6,2,6,4,2,6,4,6,8,4,2,4,2,4,14,4,6,2,10,2,6,6,4,2,4,6,2,10,2,4,2,12,10,2,4,2,4,6,2,6,4,6,6,6,2,6,4,2,6,4,6,8,4,2,4,6,8,6,10,2,4,6,2,6,6,4,2,4,6,2,6,4,2,6,10,2,10,2,4,2,4,6,8,4,2,4,12,2,6,4,2
			Data.L 6,4,6,12,2,4,2,4,8,6,4,6,2,4,6,2,6,10,2,4,6,2,6,4,2,4,2,10,2,10,2,4,6,6,2,6,6,4,6,6,2,6,4,2,6,4,6,8,4,2,6,4,8,6,4,6,2,4,6,8,6,4,2,10,2,6,4,2,4,2,10,2,10,2,4,2,4,8,6,4,2,4,6,6,2,6,4,8,4,6,8,4,2,4,2,4,8,6,4,6,6
			Data.L 6,2,6,6,4,2,4,6,2,6,4,2,4,2,10,2,10,2,6,4,6,2,6,4,2,4,6,6,8,4,2,6,10,8,4,2,4,2,4,8,10,6,2,4,8,6,6,4,2,4,6,2,6,4,6,2,10,2,10,2,4,2,4,6,2,6,4,2,4,6,6,2,6,6,6,4,6,8,4,2,4,2,4,8,6,4,8,4,6,2,6,6,4,2,4,6,8,4,2,4,2
			Data.L 10,2,10,2,4,2,4,6,2,10,2,4,6,8,6,4,2,6,4,6,8,4,6,2,4,8,6,4,6,2,4,6,2,6,6,4,6,6,2,6,6,4,2,10,2,10,2,4,2,4,6,2,6,4,2,10,6,2,6,4,2,6,4,6,8,4,2,4,2,12,6,4,6,2,4,6,2,12,4,2,4,8,6,4,2,4,2,10,2,10,6,2,4,6,2,6,4,2,4,6,6
			Data.L 2,6,4,2,10,6,8,6,4,2,4,8,6,4,6,2,4,6,2,6,6,6,4,6,2,6,4,2,4,2,10,12,2,4,2,10,2,6,4,2,4,6,6,2,10,2,6,4,14,4,2,4,2,4,8,6,4,6,2,4,6,2,6,6,4,2,4,6,2,6,4,2,4,12,2,12,0
		EndDataSection
	EndProcedure
	Define nb$,nb.q,l2nb.d,nbl2.q,nbMAX.q,NBREC.q,DIV.q,i,pas,fact_prem$,j,deb.q,mess$,quotient.q,reste.l,quotientp.q,*Tab,ind.l,idiv,SEQD.div
	Macro decompose1
		idiv=0
		Repeat
			;     ;Le nom de @@: signifie étiquette anonyme,vous pouvez avoir défini un grand nombre d'entre eux dans la source.
			;     ;Symbole @b(ou l'équivalent @r)le plus proche des références du label précédent anonyme
			;     ;,symbole @f références plus proche de l'étiquette suivante anonyme.
			;     ;Ces symboles spéciaux sont insensibles à la casse.
			;;*******************************  TESTS EN ASM ********************************************************************
			;*************************************** Division d'un nombre de 64 bits par un nombre de 32 bits ******************************************
			EnableASM
			MOV ecx,dword[v_DIV]
			XOr EDX,EDX
			MOV eax,dword[v_nb+4]
			DIV ecx
			MOV dword[v_quotientp],eax
			MOV eax,dword[v_nb]
			DIV ecx
			CMP edx,0
			JNZ @f
			;     MOV dword[v_reste],edx
			MOV edx,dword[v_quotientp]
			mov dword[v_nb+4],edx
			MOV dword[v_nb],eax
			;************************************************ Recherche de la racine carré ***************************************************************
			FILD qword[v_nb]
			FSQRT
			; !FISTTP dword [v_nbMAX] ; avec arrondi si vous décommentez cette instruction commentez la précédente
			;                           et laissez le ! car l'instruction FISTTP n'est pas reconnue par PureBasic avec !FISTTP c'est bon !!!!
			FISTP dword[v_nbMAX] ; sans arrondi
			;*********************************************** Affectation de la valeur du DIViseur dans la table *******************************************
			;     MOV ecx, [v_DIV]; à decommenter si ecx est effacée
			mov ebx, [p_Tab]
			mov edx, [v_ind]
			add ebx,edx
			mov[ebx],ecx
			add edx,8
			mov[v_ind],edx
			DisableASM
			If nb<=1:Break:EndIf
			EnableASM
			JMP lab11
			!@@:
			mov edx,[v_pas]
			ADD dword [v_DIV],edx
			DisableASM
			;********************************************************************************************************************************************************
			;********************************************************************************************************************************************************
			;*******************************************************************************************************************************************************
			If DIV=3:Break:EndIf
			If DIV>NBMAX Or div<0:Break:EndIf
		!lab11:
	ForEver
	;   !FIN#MacroExpandedCount:
EndMacro
Macro decompose2
	idiv=0
	Repeat
		;     ;Le nom de @@: signifie étiquette anonyme,vous pouvez avoir défini un grand nombre d'entre eux dans la source.
		;     ;Symbole @b(ou l'équivalent @r)le plus proche des références du label précédent anonyme
		;     ;,symbole @f références plus proche de l'étiquette suivante anonyme.
		;     ;Ces symboles spéciaux sont insensibles à la casse.
		;;*******************************  TESTS EN ASM ********************************************************************
		;*************************************** Division d'un nombre de 64 bits par un nombre de 32 bits ******************************************
		EnableASM
		MOV ecx,dword[v_DIV]
		XOr EDX,EDX
		MOV eax,dword[v_nb+4]
		DIV ecx
		MOV dword[v_quotientp],eax
		MOV eax,dword[v_nb]
		DIV ecx
		CMP edx,0
		JNZ @f
		;     MOV dword[v_reste],edx
		MOV edx,dword[v_quotientp]
		mov dword[v_nb+4],edx
		MOV dword[v_nb],eax
		;************************************************ Recherche de la racine carré ***************************************************************
		FILD qword[v_nb]
		FSQRT
		; !FISTTP qword [v_nbMAX] ; avec arrondi si vous décommentez cette instruction commentez la précédente
		;                           et laissez le ! car l'instruction FISTTP n'est pas reconnue par PureBasic avec !FISTTP c'est bon !!!!
		FISTP qword[v_nbMAX] ; sans arrondi
		;*********************************************** Affectation de la valeur du DIViseur dans la table *******************************************
		;     MOV ecx, [v_DIV]; à decommenter si ecx est effacée
		mov ebx, [p_Tab]
		mov edx, [v_ind]
		add ebx,edx
		mov[ebx],ecx
		add edx,8
		mov[v_ind],edx
		DisableASM
		If nb<=1:Break:EndIf
		EnableASM
		JMP lab#MacroExpandedCount
		!@@:
		mov edx,[v_pas]
		ADD dword[v_DIV],edx
		DisableASM
		;********************************************************************************************************************************************************
		;********************************************************************************************************************************************************
		; ;***********************************  Pour accélerer encore l' algo  *******************************
		If div=>SEQD\PREMDIV
			pas=SEQD\TDIF(idiv)
			If idiv+1=SEQD\NBSEQ
				idiv=-1
			EndIf
			idiv+1
		EndIf
		;************************************  Pour accélerer encore l' algo vous pouvez décommentez les 7 lignes PB précedentes ******************************
		;*******************************************************************************************************************************************************
		If DIV>NBMAX Or div<0:Break:EndIf
		
		!lab#MacroExpandedCount:
	ForEver
	;   !FIN#MacroExpandedCount:
EndMacro

choixdiv(SEQD)
saisie:
mess$+"Décomposition en facteur premier"
If Len(mess$)>99
	MessageRequester("Erreur","Donnez un entier positif < ou  9223372036854775807"+#CR$+"Relancez le prg") ;
	End
EndIf
nb$=InputRequester(mess$,"Donnez un entier positif < ou = 9223372036854775807","9223372036854775807") ; c'est la limite d'un type q  2^63-1
;;                                                                                   en puissance de 2=>2^62 donne le plus grand nombre de facteurs
If Len(nb$)>Len("9223372036854775807")                                         ;; en puissance de 3 => 3^39
	Goto saisie
EndIf
nb.q=Val(nb$)
If nb<1
	Goto saisie
EndIf
; si le nombre nb est   pair il peut être une puissance de 2 nb=2^n avec n positions max dans la table donc n=log2(nb)
; si le nombre nb est impair il peut être une puissance de 3 nb=3^n avec n positions max dans la table donc n=log3(nb)
If nb%2=0
	l2nb.d=Log(nb)/Log(2)
Else
	l2nb.d=Log(nb)/Log(3)
EndIf
nbl2.q=l2nb          ; conversion en nb entier
NBMAX.Q=Sqr(NB)      ;limite de recherche des facteurs premiers
NBREC.Q=1
Dim Tab.q(NBl2)
*Tab=@Tab()
DIV=2
i=0
pas=1
fact_prem$=nb$+"="
deb.q=ElapsedMilliseconds()
; decompose(DIV=3)
decompose1
;; (pas de 2 à partir du diviseur 3 on ne garde que les diviseurs impairs)
pas=2
; decompose(DIV>NBMAX)
decompose2
i=ind/8
tab(i)=nb
If tab(i)<>1
	I+1
	tab(i)=1
EndIf
For j=0 To i
	fact_prem$+tab(j)
	NBREC*tab(j) ; Vérification de la décomposition
	If j<i
		fact_prem$+"*"
	EndIf
Next
MessageRequester("Résultat",fact_prem$+#CR$+Str(NBREC)+": contrôle"+#CR$+"temps="+Str(ElapsedMilliseconds()-deb)+"ms"+#CR$+"Elimination de tous les multiples des nb premiers <=:"+Str(nbs)+#CR$+"Nombre d'éléments du vecteur =:"+Str(NBSEQ))

Et ici le code qui à généré les séquences répétitives à partir des nb premiers 2 3 5 7 ou 11;
Le programme suivant génère pour le prg de décomposition les séquences en fonction du nombre de colonnes que l’on désire éliminer
Il détermine :
1) le premier nb premier à partir duquel on applique le vecteur
2) le vecteur des éléments du modulo
3) Il se termine par 0 terme qui est la borne finale du vecteur et qui ne fait pas parti du vecteur.


Code : Tout sélectionner

 Macro _q_t_
   "
 EndMacro
 Macro _n (__n)
 _q_t_#__n#=_q_t_+Str(__n)+" "
 EndMacro
Dim T_MODULO.l(12)
Structure colonne
  prem.a
  dif_prec.l
EndStructure
; **************** Réalisation du vecteur modulo npp à partir d'une table des nombres premiers des 100 premiers nombres *********
;***** Choix du premier Nb premier poue lequel le vecteur modulo sera appliqué.
;***** pour éviter la génération d'un vesteur trop important nous limiterons ce choix aux 11 premiers nombres premiers soit :2 3 5 7 11 13 17 19 23 29 31
;***** Recherche du modulo < 2*3*5*7*11=2310 éléments du vecteur
SAISIE0:
mess$+"Filtre de réduction des diviseurs"
If Len(mess$)>120
  MessageRequester("Erreur","Colonne Div max 2 3 5 7 11 13 17 19 23 29 31"+#CR$+"Relancez le prg") ;
  End
EndIf
nb$=InputRequester(mess$,"Colonne Div max 2 3 5 7 11 13 17 19 23 29 31","5") ;
If Len(nb$)>Len("31")
EndIf
nbs=Val(nb$)
If nbs<1 Or nbs>31
  Goto SAISIE0
EndIf

FINSAISIE0:
Restore lab_pnbp
i=0
Modulo=1
Repeat
  Read.l ELEM
  If ELEM<>0
    T_modulo(I)=elem
    Modulo*elem
    i+1
  EndIf
Until ELEM=0 Or ELEM=>nbs
NBprem=i
nbs=ELEM
Dim tcol.colonne(modulo+2)
;*** Recherche des colonnes ayant des nb premiers ***
tcol(0)\prem=2
tcol(1)\prem=2

For inb=2 To modulo+1
  For inbp=0 To nbprem-1
    If inb%t_modulo(inbp)=0
      tcol(inb)\prem=2
    EndIf
  Next
Next  
prem_p=0
PREM_NB_PREM_AV=0
NB_PREM=0
SOM_DIF=0
vecteur$="DIV_"+Str(nbs)+":"+#CRLF$
;****** Recherche des différence entre NB premiers *****  
For inb=2 To modulo+1
  If tcol(inb)\prem=0 And inb > nbs
    If prem_p=0
      prem_p=inb
      PREM_NB_PREM_AV=inb
      vecteur$+"DATA.L  "+Str(inb)+","
    Else
      NB_PREM+1 
      If nb_prem%101=0
        vecteur$+Str(inb-prem_p)+#CRLF$+"Data.L "
        tcol(inb)\dif_prec=inb-prem_p
;         Debug _NL+_n(NB_prem)+_n(prem_p)+_n( tcol(inb)\dif_prec)
        SOM_DIF+(inb-prem_p)
        prem_p=inb
      Else
        tcol(inb)\dif_prec=inb-prem_p
        vecteur$+Str(inb-prem_p)+","
;         Debug _NL+_n(nb_prem)+_n(prem_p)+_n( tcol(inb)\dif_prec)
        SOM_DIF+(inb-prem_p)
        prem_p=inb
      EndIf
    EndIf
  EndIf   
Next 
;  tcol(modulo+2)\dif_prec=nb_prem+modulo-(modulo+1)

tcol(modulo+2)\dif_prec=PREM_NB_PREM_AV-1
SOM_DIF+(PREM_NB_PREM_AV-1)
vecteur$+Str(PREM_NB_PREM_AV-1)+",0"
If CreateFile(0, "DIV_"+Str(nbs)+".PB")         ; création d'un nouveau fichier texte...
      WriteString(0, vecteur$ ) ;
      CloseFile(0)              ; ferme le fichier précédemment ouvert et enregistre les données
      MessageRequester("C'est tout bon","Somme des nb du vecteur="+_n(SOM_DIF)+#CRLF$+_n(modulo)+#CRLF$+vecteur$+#CRLF$+"Fichier: "+GetCurrentDirectory()+"\DIV_"+Str(nbs)+".PB")
  Else
    MessageRequester("Information","Impossible de créer le fichier! DIV_"+Str(nbs)+".PB")
  EndIf



DataSection
  lab_pnbp:
  Data.l 2,3,5,7,11,13,17,19,23,29,31,0
EndDataSection
; ***************** Ci dessous les Nombres premiers pour les 1000 premiers nombres
; 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97
; 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199
; 211 223 227 229 233 239 241 251 257 263 269 271 277 281 283 293
; 307 311 313 317 331 337 347 349 353 359 367 373 379 383 389 397
; 401 409 419 421 431 433 439 443 449 457 461 463 467 479 487 491 499
; 503 509 521 523 541 547 557 563 569 571 577 587 593 599
; 601 607 613 617 619 631 641 643 647 653 659 661 673 677 683 691
; 701 709 719 727 733 739 743 751 757 761 769 773 787 797
; 809 811 821 823 827 829 839 853 857 859 863 877 881 883 887
; 907 911 919 929 937 941 947 953 967 971 977 983 991 997


Avec le prg de décomposition j'ai obtenu avec le nombre 9223372036852775807 à décomposer
et en éliminant avec :
1) 2 => 34956 ms
2) 3 => 23026 ms
3) 5 => 20251 ms
4) 7 => 16101 ms
5) 11 => 14441 ms

A+
Dernière modification par PAPIPP le jeu. 17/nov./2016 8:34, modifié 4 fois.
Il est fort peu probable que les mêmes causes ne produisent pas les mêmes effets.(Einstein)
Et en logique positive cela donne.
Il est très fortement probable que les mêmes causes produisent les mêmes effets.
Frenchy Pilou
Messages : 2194
Inscription : jeu. 27/janv./2005 19:07

Re: Décomposition d’un nombre en produit de facteurs premier

Message par Frenchy Pilou »

Nickel! 8) il faudrait juste réorganiser le résultat en ordre croissant!
9699690 :)
= 2*3*5*7*11*13*17*19*1
en
= 1*2*3*5*7*11*13*17*19

et que donne 1*3*11971*34408463 ? :)
Est beau ce qui plaît sans concept :)
Speedy Galerie
PAPIPP
Messages : 534
Inscription : sam. 23/févr./2008 17:58

Re: Décomposition d’un nombre en produit de facteurs premier

Message par PAPIPP »

Bonjour à tous
et merci Frenchy Pilou
C'est bien vrai mais actuellement j'essaie de diminuer le temps d’exécution.

Voici une nouvelle version plus rapide.

Code : Tout sélectionner

; algorithme de DECOMPOSITION EN FACTEURS_PREMIERS
; Le nombre 1 n'est pas par convention un nombre premier.
; Je l'ai placé malgré cela dans le produit de facteur. Vous pouvez le retirer
EnableExplicit
DisableDebugger
Structure DIV
  PREMDIV.l
  NBSEQ.l
  Array TDIF.l(3000)
EndStructure
Global nbs.l,NBSEQ.l

Procedure choixdiv(*EL.DIV)
  Protected mess$, nb$, ELEM, ipas, i
  ;********************************************* Choix du filtre à tester *********************************
  nbs=7
  ;   Goto FINSAISIE0 ;;;; si vous ne désirez plus choisir les multiples des nb premiers à éliminer commentez cette ligne et imposer nbs juste au dessus
  SAISIE0:
  mess$+"Filtre de réduction des diviseurs"
  If Len(mess$)>120
    MessageRequester("Erreur","Eliminer les multiples des nb premiers <= à  2 3 5 7 11"+#CR$+"Relancez le prg") ;
    End
  EndIf
  nb$=InputRequester(mess$,"Eliminer les multiples des nb premiers <= à 2 3 5 7 11","7") ;
  If Len(nb$)>Len("11")
    Goto SAISIE0 
  EndIf
  nbs=Val(nb$)
  If nbs<1 Or nbs>11
    Goto SAISIE0
  EndIf
  FINSAISIE0:
  ; ***************************  Chargement de la séquence à tester ******************************
  Select nbs
    Case 1,2
      Restore DIV_2
    Case 3,4
      Restore DIV_3
    Case 5,6
      Restore DIV_5
    Case 7 To 9
      Restore DIV_7
    Case 10 To 11
      Restore DIV_11
      
  EndSelect
  Read.l *EL\PREMDIV
  i=0
  Repeat
    Read.l ELEM
    If ELEM<>0
      *EL\TDIF(I)=elem
      i+1
    EndIf
  Until ELEM=0
  *EL\NBSEQ=I
  NBSEQ=I
  ipas=0
  DataSection
    DIV_2:;;;***** 3 est le premier diviseur auquel la séquence s'applique Simple élimination des nombres pairs
    Data.l 3,2,0; 
    DIV_3:;;***** 5 est le premier diviseur auquel la séquence s'applique pour 2*3=6 gain de 30% environ élimination des multiples 2 3
    Data.l 5,2,4,0;  
    DIV_5:; ***** 7 est le premier diviseur auquel la séquence s'applique pour 2*3*5=30, élimination des multiples 2 3 5
    Data.l 7,4,2,4,2,4,6,2,6,0 
    DIV_7: ;;*****  11 est le premier diviseur auquel la séquence s'applique pour 2*3*5*7=210, élimination des multiples de 2 3 5 7
    Data.l 11,2,4,2,4,6,2,6,4,2,4,6,6,2,6,4,2,6,4,6,8,4,2,4,2,4,8,6,4,6,2,4,6,2,6,6,4,2,4,6,2,6,4,2,4,2,10,2,10,0
    DIV_11: ;;1**** 13 est le premier diviseur auquel la séquence s'applique pour 2*3*5*7*11=2310, élimination des multiples de 2 3 5 7 11
    Data.L  13,4,2,4,6,2,6,4,2,4,6,6,2,6,4,2,6,4,6,8,4,2,4,2,4,14,4,6,2,10,2,6,6,4,2,4,6,2,10,2,4,2,12,10,2,4,2,4,6,2,6,4,6,6,6,2,6,4,2,6,4,6,8,4,2,4,6,8,6,10,2,4,6,2,6,6,4,2,4,6,2,6,4,2,6,10,2,10,2,4,2,4,6,8,4,2,4,12,2,6,4,2
    Data.L 6,4,6,12,2,4,2,4,8,6,4,6,2,4,6,2,6,10,2,4,6,2,6,4,2,4,2,10,2,10,2,4,6,6,2,6,6,4,6,6,2,6,4,2,6,4,6,8,4,2,6,4,8,6,4,6,2,4,6,8,6,4,2,10,2,6,4,2,4,2,10,2,10,2,4,2,4,8,6,4,2,4,6,6,2,6,4,8,4,6,8,4,2,4,2,4,8,6,4,6,6
    Data.L 6,2,6,6,4,2,4,6,2,6,4,2,4,2,10,2,10,2,6,4,6,2,6,4,2,4,6,6,8,4,2,6,10,8,4,2,4,2,4,8,10,6,2,4,8,6,6,4,2,4,6,2,6,4,6,2,10,2,10,2,4,2,4,6,2,6,4,2,4,6,6,2,6,6,6,4,6,8,4,2,4,2,4,8,6,4,8,4,6,2,6,6,4,2,4,6,8,4,2,4,2
    Data.L 10,2,10,2,4,2,4,6,2,10,2,4,6,8,6,4,2,6,4,6,8,4,6,2,4,8,6,4,6,2,4,6,2,6,6,4,6,6,2,6,6,4,2,10,2,10,2,4,2,4,6,2,6,4,2,10,6,2,6,4,2,6,4,6,8,4,2,4,2,12,6,4,6,2,4,6,2,12,4,2,4,8,6,4,2,4,2,10,2,10,6,2,4,6,2,6,4,2,4,6,6
    Data.L 2,6,4,2,10,6,8,6,4,2,4,8,6,4,6,2,4,6,2,6,6,6,4,6,2,6,4,2,4,2,10,12,2,4,2,10,2,6,4,2,4,6,6,2,10,2,6,4,14,4,2,4,2,4,8,6,4,6,2,4,6,2,6,6,4,2,4,6,2,6,4,2,4,12,2,12,0
  EndDataSection
EndProcedure

Define nb$,nb.q,l2nb.d,nbl2.q,nbMAX.q,NBREC.q,DIV.l,i,pas,fact_prem$,j,deb.q,mess$,quotient.q,reste.l,quotientp.q,*Tab,ind.l,idiv,SEQD.div,AA$,MDIV,MPAS
Macro decompose1(TEST_)
  Repeat
    ;     ;Le nom de @@: signifie étiquette anonyme,vous pouvez avoir défini un grand nombre d'entre eux dans la source.
    ;     ;Symbole @b(ou l'équivalent @r)le plus proche des références du label précédent anonyme
    ;     ;,symbole @f références plus proche de l'étiquette suivante anonyme.
    ;     ;Ces symboles spéciaux sont insensibles à la casse.
    ;;*******************************  TESTS EN ASM ********************************************************************
    ;*************************************** Division d'un nombre de 64 bits par un nombre de 32 bits ******************************************
    EnableASM
    MOV ecx,dword[v_DIV]
    XOr EDX,EDX
    MOV eax,dword[v_nb+4]
    DIV ecx
    MOV dword[v_quotientp],eax
    MOV eax,dword[v_nb]
    DIV ecx
    CMP edx,0
    JNZ @f
    ;     MOV dword[v_reste],edx
    MOV edx,dword[v_quotientp]
    mov dword[v_nb+4],edx
    MOV dword[v_nb],eax
    ;************************************************ Recherche de la racine carré ***************************************************************
    FILD qword[v_nb]
    FSQRT
    ; !FISTTP dword [v_nbMAX] ; avec arrondi si vous décommentez cette instruction commentez la précédente
    ;                           et laissez le ! car l'instruction FISTTP n'est pas reconnue par PureBasic avec !FISTTP c'est bon !!!!
    FISTP dword[v_nbMAX] ; sans arrondi
    ;*********************************************** Affectation de la valeur du DIViseur dans la table *******************************************
    ;     MOV ecx, [v_DIV]; à decommenter si ecx est effacée
    mov ebx, [p_Tab]
    mov edx, [v_ind]
    add ebx,edx
    mov[ebx],ecx
    add edx,8
    mov[v_ind],edx
    DisableASM
    If nb<=1:Break:EndIf
    EnableASM
    JMP lab11#MacroExpandedCount
    !@@:
    mov edx,[v_pas]
    ADD[v_DIV],edx
    DisableASM
    ;********************************************************************************************************************************************************
    ;********************************************************************************************************************************************************
    ;*******************************************************************************************************************************************************
    If TEST_:Break:EndIf
    If DIV>NBMAX Or div<0:Break:EndIf
    !lab11#MacroExpandedCount:
;     Debug _n(div)
  ForEver
EndMacro
Macro decompose2
      pas=SEQD\TDIF(0)
    idiv=1
  Repeat
  
    ;     ;Le nom de @@: signifie étiquette anonyme,vous pouvez avoir défini un grand nombre d'entre eux dans la source.
    ;     ;Symbole @b(ou l'équivalent @r)le plus proche des références du label précédent anonyme
    ;     ;,symbole @f références plus proche de l'étiquette suivante anonyme.
    ;     ;Ces symboles spéciaux sont insensibles à la casse.
    ;;*******************************  TESTS EN ASM ********************************************************************
    ;*************************************** Division d'un nombre de 64 bits par un nombre de 32 bits ******************************************
    EnableASM
    MOV ecx,dword[v_DIV]
    XOr EDX,EDX
    MOV eax,dword[v_nb+4]
    DIV ecx
    MOV dword[v_quotientp],eax
    MOV eax,dword[v_nb]
    DIV ecx
    CMP edx,0
    JNZ @f
    ;     MOV dword[v_reste],edx
    MOV edx,dword[v_quotientp]
    mov dword[v_nb+4],edx
    MOV dword[v_nb],eax
    ;************************************************ Recherche de la racine carré ***************************************************************
    FILD qword[v_nb]
    FSQRT
    ; !FISTTP dword [v_nbMAX] ; avec arrondi si vous décommentez cette instruction commentez la précédente
    ;                           et laissez le ! car l'instruction FISTTP n'est pas reconnue par PureBasic avec !FISTTP c'est bon !!!!
    FISTP dword[v_nbMAX] ; sans arrondi
    ;*********************************************** Affectation de la valeur du DIViseur dans la table *******************************************
    ;     MOV ecx, [v_DIV]; à decommenter si ecx est effacée
    mov ebx, [p_Tab]
    mov edx, [v_ind]
    add ebx,edx
    mov[ebx],ecx
    add edx,8
    mov[v_ind],edx
    DisableASM
    If nb<=1:Break:EndIf
    EnableASM
    JMP lab#MacroExpandedCount
    !@@:
    mov edx,[v_pas]
    ADD[v_DIV],edx
    DisableASM
    ;********************************************************************************************************************************************************
    ;********************************************************************************************************************************************************
    ; ;***********************************  Pour accélerer encore l' algo  *******************************
    pas=SEQD\TDIF(idiv)
    If idiv+1=SEQD\NBSEQ
      idiv=-1
    EndIf
    idiv+1
    ;************************************  Pour accélerer encore l' algo vous pouvez décommentez les 7 lignes PB précedentes ******************************
    ;*******************************************************************************************************************************************************
    !lab#MacroExpandedCount:
    If DIV>NBMAX Or DIV<0:Break:EndIf
  ForEver
EndMacro

choixdiv(SEQD)
saisie:
mess$+"Décomposition en facteur premier"
If Len(mess$)>99
  MessageRequester("Erreur","Donnez un entier positif < ou  9223372036854775807"+#CR$+"Relancez le prg") ;
  End
EndIf
nb$=InputRequester(mess$,"Donnez un entier positif < ou = 9223372036854775807","9223372036854775807") ; c'est la limite d'un type q  2^63-1
;;                                                                                   en puissance de 2=>2^62 donne le plus grand nombre de facteurs
If Len(nb$)>Len("9223372036854775807")                                                                ;; en puissance de 3 => 3^39
  Goto saisie
EndIf
nb.q=Val(nb$)
If nb<1
  Goto saisie
EndIf
; si le nombre nb est   pair il peut être une puissance de 2 nb=2^n avec n positions max dans la table donc n=log2(nb)
; si le nombre nb est impair il peut être une puissance de 3 nb=3^n avec n positions max dans la table donc n=log3(nb)
If nb%2=0
  l2nb.d=Log(nb)/Log(2)
Else
  l2nb.d=Log(nb)/Log(3)
EndIf
nbl2.q=l2nb          ; conversion en nb entier
NBMAX.Q=Sqr(NB)      ;limite de recherche des facteurs premiers
NBREC.Q=1
Dim Tab.q(NBl2)
*Tab=@Tab()
DIV=2
i=0
pas=1
fact_prem$=nb$+"="
deb.q=ElapsedMilliseconds()
decompose1(DIV=3)
;; (pas de 2 à partir du diviseur 3 on ne garde que les diviseurs impairs)
Debug _n(div)
pas=2
decompose1(DIV=SEQD\PREMDIV)

decompose2
i=ind/8
tab(i)=nb
If tab(i)<>1
  I+1
  tab(i)=1
EndIf
For j=0 To i
  fact_prem$+tab(j)
  NBREC*tab(j) ; Vérification de la décomposition
  If j<i
    fact_prem$+"*"
  EndIf
Next
MessageRequester("Résultat",fact_prem$+#CR$+Str(NBREC)+": contrôle"+#CR$+"temps="+Str(ElapsedMilliseconds()-deb)+"ms"+#CR$+"Elimination de tous les multiples des nb premiers <=:"+Str(nbs)+#CR$+"Nombre d'éléments du vecteur =:"+Str(NBSEQ))



Avec ce prg de décomposition j'ai obtenu avec le nombre 9223372036852775807 à décomposer
et en éliminant avec :
1) 2 => 30791 ms
2) 3 => 22360 ms
3) 5 => 19315 ms
4) 7 => 15360 ms
5) 11 => 13747 ms

A+
Il est fort peu probable que les mêmes causes ne produisent pas les mêmes effets.(Einstein)
Et en logique positive cela donne.
Il est très fortement probable que les mêmes causes produisent les mêmes effets.
Ollivier
Messages : 4197
Inscription : ven. 29/juin/2007 17:50
Localisation : Encore ?
Contact :

Re: Décomposition d’un nombre en produit de facteurs premier

Message par Ollivier »

Bonjour Papipp,

sur ce site, tu as vraiment un paquet de règles de maths. Il y a quelques petites fautes de frappes mais c'est franchement bien diversifié:

http://www.villemin.gerard.free.fr/Wwwg ... tm#Premier
PAPIPP
Messages : 534
Inscription : sam. 23/févr./2008 17:58

Re: Décomposition d’un nombre en produit de facteurs premier

Message par PAPIPP »

Merci Ollivier.

Ton lien http://www.villemin.gerard.free.fr/Wwwg ... tm#Premier est mort mais je connaissais.
Voici le lien http://villemin.gerard.free.fr/Wwwgvmm/ ... troduc.htm.

C'est un site très bien fait.

Ce qui m’intéresse le plus ce sont les démonstrations.
Par exemple j'ai démontré pourquoi aucun nombre premier ne peut être oublié dans la séquence.
2 3 5 +(2 4) ici en répétition en boucle jusqu'à l'infini c'est à dire en développant :
2 3 5 (5+2)=7 (7+4)=11 (11+2)=13 (13+4)=17 (17+2)=19 (19+4)=23 .etc..jusqu'à l'infini (+2 +4)

Ou dans cette autre séquence.
2 3 5 7 +(4 2 4 2 4 6 2 6) en répétition en boucle jusqu'à l'infini.

etc...

Or c'est en cherchant à diminuer le nombre de diviseur que l'on arrive à cette conclusion. Dans ces séquences on ne peut oublier de nombre premier. Par contre il reste des diviseurs inutiles qui sont les multiples des Nombres premiers > au dernier exprimé 3 dans le premier exemple et 5 dans le deuxième exemple.
Il est fort peu probable que les mêmes causes ne produisent pas les mêmes effets.(Einstein)
Et en logique positive cela donne.
Il est très fortement probable que les mêmes causes produisent les mêmes effets.
Répondre