PureBasic

Loin du pragmatisme informatique, ma question principale est :
"Est-il préférable de virtualiser une période de taille p-factorielle?
Ou bien est-il préférable de choisir une p-factorielle élevée pour couvrir tout le domaine balayable et de virtualiser un système linéaire?"

J'ai des doutes négatifs pour la 2nde, et des doutes positifs pour la 1ère. Mais, j'ai constaté, relativement souvent que ce type d'appréciation personnelle ne me conduisait pas aux chemins les plus judicieux.

Par exemple, j'ai une absence totale d'expériences sur la compression des gaps. Je m'étais aventuré dans cette direction, il y a un peu plus de 20 ans sur papier. Seulement, le temps a eu raison de ces infos. J'ai "heureusement" une mémoire assez étrange : en reprenant le contexte de l'époque, je peux réécrire pas à pas, ce j'avais écrit, et je me souviens m'être subitement passionné par ce truc en griffonnant devant X-Files. Résultat : il faut que je me rebouffe tous les épisodes de X-Files pour rester constructif...

Quand il faut y aller, faut y aller !

J'ai bien réfléchi à la question de la compression en mémoire, en utilisant une table en bits. Pour repartir sur quelque chose de facile à lire, j'ai repris un crible simple, bourrin, qui marque les multiples de tous les impairs. C'est vraiment pas malin mais ça donne une base de mesure pour aboutir à l'accès aux nombres premiers (ou au moins au décompte de ceux-ci).

Je choisi de rester en PB sans fioritures FASM. Mais je me suis quand même amusé à optimiser à la mano. Pour info, en optimisant vraiment aux taquets, on divise le temps par 3. Ce qui n'est pas moche. Si on envoie le boulot sur les 4 pattes du cloporte, ça pourrait aller dix fois plus vite donc en optimisé assembleur.

Deux code proposés pour le musée : le premier utilise une table de nmax bits, chaque bit représentant une valeur de 0 à nmax. Le but du jeu est de marquer les bits comme il faut et de savoir ensuite les pointer correctement. Pas trop compliqué, chaque octet représente une suite de 8 nombres entiers consécutifs.

Le second code fait le même boulot, mais travaille sur la partition de N ne contenant que les impairs. Du coup on stocke 2 fois plus de nombres dans le tableau en quelque sorte. Le premier code est juste pour remontrer ce qui a déjà été proposé je crois ici, le plus intéressant est peut-être le second sur la manière de faire correspondre les bits du tableau aux nombres qu'ils représentent. J'ai rédigé de manière, en principe, à ce que ça tourne sur x86, mais pas testé,

Avantage de la représentation en bits, compression d'un facteur 8 si on représente N, et d'un facteur 16 si on représente la partition 2i+1 (les impairs). Pas trop utile d'aller chercher un algorithme de compression dans ces conditions, si le temps d'accès à un bit est pas trop vilain. Justement à propos de temps, ça ne vaudra jamais les performances obtenues dans mon programme clef du moment. Les manipulations de bits coûtent quand même un poil (même en allant tirer les cheveux de l'assembleur).

Après avoir testé un peu tous les modes de traitement bit (en PB et en assembleur), voici ce qui semble fonctionner le mieux en PB. Pour l'assembleur, dès lors qu'on fait correspondre une valeur n à 1 octet et à 1 bit, l'utilisation des fonctions bt et bts est sauvagement recommandée (mais attention aux problèmes de format de registres, ces petites bêtets n'aiment que les byte et word, et pas vraiment les dword, qword, et autres).

Donc en langue PB ça donne ce qui suit (temps à la lcouhe sur ma machine de référence pour 1e8, 5s pour le premier, et 3s pour le second)

Code : Tout sélectionner

Structure NOTHING
EndStructure

Define.NOTHING

PrintFlag.i = #True
PrintFlag.i = #False
nmin.i = 0
nmax.i = 1e8

OpenConsole()

tz.i = ElapsedMilliseconds()

PageSize.I = nmax / 8
If PageSize * 8 < nmax
  PageSize + 1
EndIf

AvailablePhysicalMemory.i = MemoryStatus(#PB_System_FreePhysical)
RequiredArraySize.i = PageSize


PrintN("AvailablePhysicalMemory : " + FormatNumber(AvailablePhysicalMemory, 0, ",", "."))
PrintN("RequiredArraySize : " + FormatNumber(RequiredArraySize, 0, ",", "."))
If AvailablePhysicalMemory - RequiredArraySize < 50e6
  If MessageRequester("Warning", "Available physical memory will not make it easy. Continue ?", #PB_MessageRequester_YesNoCancel) <> #PB_MessageRequester_Yes
    End
  EndIf
EndIf

Dim Page.b(PageSize)
nPrimes.i = 0
CellIndex.i
BitIndex.i

dmax.i = Sqr(nmax)
For d.i = 3 To dmax Step 2
  n.i = d << 1
  Repeat
    CellIndex = n >> 3
    BitIndex = n - CellIndex << 3
    Page(CellIndex) | 1 << BitIndex
    n + d
  Until n > nmax
Next

Page(0) | $02 ; cancel 1 in primes list

If PrintFlag
  Print("2 ")
EndIf

For CellIndex = 0 To PageSize
  For BitIndex = 1 To 7 Step 2
    n = CellIndex << 3 + BitIndex
    If n > nmax
      Break
    EndIf
    If n & 1 = 1
      If Not Page(CellIndex) & (1 << BitIndex) ; IsPrime
        If PrintFlag
          Print(Str(n) + " ")
        EndIf
        nPrimes + 1
      EndIf
    EndIf
  Next BitIndex
Next CellIndex

nPrimes + 1

If PrintFlag
  PrintN("")
EndIf

Time.d = (ElapsedMilliseconds() - tz) / 1000

PrintN("Range 0-" + FormatNumber(nmax, 0, ",", ".") + #TAB$ + FormatNumber(nPrimes, 0, ",", ".") + " primes found in " + StrD(Time, 3) + " s")
PrintN("")
PrintN("Push any key to quit ...")
While Inkey() = ""
  Delay(50)
Wend
CloseConsole()

CallDebugger
End

Code : Tout sélectionner

Structure NOTHING
EndStructure

Define.NOTHING

PrintFlag.i = #True ; PrintFlag pour dire qu'on veut afficher les premiers à l'écran ou pas.
PrintFlag.i = #False
nmin.i = 0 ; juste pour dire qu'on démarre de 0
nmax.i = 1e8 ; La plage 1e8 est assez rapide, mais plus ça peut devenir un peu long

If PrintFlag = #True And nmax > 1e5
  If MessageRequester("Attention", "Voulez-vous vraiment lister tous ces nombres à l'écran", #PB_MessageRequester_YesNoCancel) = #PB_MessageRequester_No
    PrintFlag = #False
  EndIf
EndIf

OpenConsole()

tz.i = ElapsedMilliseconds()

PageSize.i = nmax / 16 ; La taille du tableau pour le crible est donnée pour le nombre d'entiers testés, en ne prenant que les impairs représentés sous forme de bits.
If PageSize * 16 < nmax
  PageSize + 1
EndIf

AvailablePhysicalMemory.i = MemoryStatus(#PB_System_FreePhysical)
RequiredArraySize.i = PageSize


PrintN("AvailablePhysicalMemory : " + FormatNumber(AvailablePhysicalMemory, 0, ",", "."))
PrintN("RequiredArraySize : " + FormatNumber(RequiredArraySize, 0, ",", "."))
If AvailablePhysicalMemory - RequiredArraySize < 50e6
  If MessageRequester("Attention", "La mémoire vive disponible ne va pas rendre les choses faciles. Continuer ?", #PB_MessageRequester_YesNoCancel) <> #PB_MessageRequester_Yes
    End
  EndIf
EndIf

Dim Page.b(PageSize) ; On utilise donc un tableau binaire avec un accès à l'octet.
nPrimes.i = 0
CellIndex.i
BitIndex.i

dmax.i = Sqr(nmax)
For d.i = 3 To dmax Step 2 ; On passe au crible avec les diviseurs impairs
  n.i = d << 1 ; On ne crible pas n / d avec n = d.
  Repeat
    If n & 1 ; si n est impair
      CellIndex = n >> 4 ; on utilise l'offset modulo 16
      BitIndex = (n - CellIndex << 4) >> 1 ; que l'on divise par 2 pour avoir une position en bit d'un octet
      Page(CellIndex) | 1 << BitIndex ; on met le bit correspondant à la valeur 1 (marquage d'un composite)
    EndIf
    n + d ; on fait avancer le pointeur de crible
  Until n > nmax ; jusqu'à la fin du tableau
Next ; et on continue avec la valeur de crible suivante

Page(0) | $01 ; effacer le nombre 1 de la liste

If PrintFlag
  Print("2 ") ; le nombre 2 étant pair et non traité !
EndIf

For CellIndex = 0 To PageSize ; Pour chaque octet du tableau
  For BitIndex = 0 To 7 ; on test bit après bit
    n = CellIndex << 4 + BitIndex << 1 + 1 ; on reconstitue la valeur n représentée par un bit
    If n > nmax ; on limite le décompte précisément à nmax, car il peut rester des bits du tableau "hors plage"
      Break
    EndIf
    If Not Page(CellIndex) & (1 << BitIndex) ; si le bit est à 0
      If PrintFlag
        Print(Str(n) + " ")
      EndIf
      nPrimes + 1
    EndIf
  Next BitIndex
Next CellIndex

nPrimes + 1

If PrintFlag
  PrintN("")
EndIf

Time.d = (ElapsedMilliseconds() - tz) / 1000

PrintN("Plage 0-" + FormatNumber(nmax, 0, ",", ".") + #TAB$ + FormatNumber(nPrimes, 0, ",", ".") + " premiers trouvés en " + StrD(Time, 3) + " s")
PrintN("")
PrintN("Appuyer entrée pour terminer ...")
Input()
CloseConsole()

CallDebugger
End

Voilà, pour l'essentiel sur ce point.

D'autre part, j'ai pris le temps de regarder sous différentes formes possibles ce que peut permettre de faire une approche telle que décrite en particulier par Ollivier. En fait il s'agit de mettre en place une arithmétique de partitionnement justement (on en parle déjà plus haut dans ce message).

Partitionner N, c'est en fait créer des sous-ensembles régis par une loi ...simple de préférence.

Sur les tests de primalité, le partitionnement battu et rebattu, par des gens qui en font sans le savoir ou d'autre en le sachant très bien, c'est le partitionnement de type 6i-+1 (6 i plus ou moins 1).

Ce type de partitionnement consiste à dire qu'on peut représenter tous les nombres de l'ensemble N en les classant en 6 catégories selon la valeur de leur modulo 6.

On aura donc les partitions répondant aux valeurs suivantes (6i+0), (6i+1), (6i+2), (6i+3), (6i+4), (6i+5) ou tous les nombres seront soit multiples de 6, soit supérieurs de 1 à un multiple de 6, etc ...

De fait on comprendra très vite que tous les nombres de la partition 6i+0 (que l'on peut appeler par son prénom 6i) sont des multiples de 6. Les nombres de la partition 6i+2 sont des multiples de 2 à coup sûr, et ceux de la partition 6i+4 aussi. Dans la mesure où 6 est un nombre pair, quelle que soit la valeur de i, 6i+0, 6i+2 et 6i+4 sont pairs c'est sûr. Et les nombres de la partition 6i+3 sont forcément des multiples de 3, puisque 6 est un multiple de 3, et que toute forme 3i+3 est nécessairement multiple de 3.

Du coup ... pas la peine de tester les nombres des partitions 6i, 6i+2, 6i+3 et 6i+4.

Pince-mi et pince-moi sont dans un bâteau ....

On peut ne travailler que sur les nombres de la forme 6i+1 et 6i+5 on est sûr d'y trouver des premiers, ... mais pas que. Il faut quand même tester les nombres restants. Cela divise le travail par trois, puisqu'on élimine 4 partitions sur les 6. Il n'y a que les premières valeurs dans n, de 0 à n, qu'il faut exclure d'un filtrage algorithmique simple, le reste est filtré de manière certaine dans les partitions.

Il y a pas mal de sources utilisant ce type de filtrage pour accélérer la recherche de nombres premiers dans une plage (ou la recherche de facteurs premiers).

J'ai testé pas mal de choses, mais pas de miracle. Gérer le partitionnement a un coût, et ne donne pas de résultats satisfaisants avec la vectorisation SSE/AVX.

Par contre je n'ai pas terminé tout à fait d'en découdre avec les différents scenarii de test, et si je trouve quelque chose de remarquable je vous en ferai part ici.

J'ai quand même aussi été pousser le bouchon du partitionnement plus loin pour tenter de pouvoir bien répondre, et en connaissance de cause, aux tentatives d'Ollivier.

Partitionner en 6 groupes, comme on vient de le voir permet de réduire la quantité de nombres à tester. On peut alors choisir de découper la plage 0, nmax en partitions pour diminuer la taille du stockage, et en découpant bien les choses, la taille du stockage pendant le travail du crible peut correspondre à une seule partition à la fois par exemple. Du coup on peut faire passer en quelque sorte six fois plus de nombres dans une zone mémoire délimitée (c'est une vue de l'esprit). Ou on peut choisir de tenter un traitement des partitions en parallèle (mais pour l'heure je n'arrive pas à des résultats intéressants en la matière).

Je suis donc allé plus loin en me disant que le schéma de partitionnement pouvait être généralisé. L'étape suivante est de partitionner n en 30 sous-ensembles des nombres de catégorie (30i), (30i+1) (30i+2) ... (30i+29). C'est à dire le partitionnement selon une loi n module 30. Pourquoi 30 ? Parce que si 6 = 2 x 3, 30 = 2 x 3 x 5 ...

Le truc marrant c'est que ce partitionnement modulo 30 donne 30 colonnes dont 8 seulement contiennent des premiers. Sur les 30 colonnes, une fois éliminé les colonnes multiples de 2, de, 3, de 5 ... il en reste 8 sur 30. Et si on pousse le raisonnement plus loin ? On augmente le nombre de colonnes, on diminue la quantité de nombres à tester ... ça pourrait être intéressant ... sauf que ça coûte un bras pour gérer tout ça au mieux dans un programme. Ca ne va pas pouvoir permettre d'accélérer le traitement dans le fond. Parce que dans les colonnes de partitionnement, les nombres premiers ne sont jamais alignés de manière prévisible (sinon ça se saurait

). Et comme l'alignement horizontal n'est pas au rendez-vous, adieu la vectorisation.

Pourtant ça me plaisait bien ce partitionnement par 30 avec 8 colonnes seulement à réellement exploiter. Si on écrit un algo qui stocke sous forme de bits, les huit colonnes utiles du système modulo 30 sont alignées sur des octets. J'essayerai quand même de vous l'écrire en PB celle-là. Mais ça peut prendre des heures le jour où je suis centré (j'ai retiré le préfixe du mot pour la modération).

Juste pour finir sur le partitionnement de N en modulos.

Le premier partitionnement qu'on fait tous naturellement .... tous les nombres premiers sauf 2 sont impairs. Il y a des impairs non premiers, mais tous les premiers sauf 2 sont impairs. C'est un partitionnement modulo 2 !

Donc modulo 2 (p-fact(2)), deux colonnes, une seule est utile pour trouver les premiers, à l'exception des plus petits. Modulo 6(p-fact(3)) , 6 colonnes, 2 sont utiles pour trouver les premiers ... modulo 30 (p-fact(5)), on a 8 colonnes utiles ....

Pour p-fact(i) on aura 48 colonnes utiles. La série correspondantes au nombres de partitions contenant des premiers parmi les partitions modulo répond à la logique p-fact(n) => 2 x 3 x 5 x 7 x 11 x ... x n, Putiles = 1 x 2 x 4 x 6 x 10 ... x (n - 1)

Bon c'est très joli, théorique, mais pratiquement ça marie pas nos filles.

C'est la minute indispensable de Monsieur Piclocède. Car demain est un autre jour.

C'est très intéressant, merci de vulgariser un peu ! J'ai parlé un peu à Ollivier du code sur les bits, je ne m'y suis pas encore attelé car je suis sur autre chose. Grâce au partitionnement, on devrait quand même y gagner, y compris sur ton code, non seulement en espace, mais aussi en rapidité. Le tout est de bien gérer le cache, avec un partitionnement adéquat, et une bonne utilisation des registres.
Les colonnes pourraient aussi correspondre à un criblage par masque. Mais c'est quand même assez compliqué à calculer, même si ça permettrait sûrement de gagner un peu de temps.

Bonjour à tous

Voici un prg basé sur la partition en fonction du p_fact(x)=Modulo.
Comme il a été démontré précédemment. On peut créer une matrice de tous les nombres naturels =>0 en prenant le reste de la division par modulo comme Numéro de colonne et la partie entière comme numéro de ligne.. Ici nous n’aurons pas besoin du numéro de ligne ou plutôt le numéro de ligne sera fictif. Cela nous permet d’optimiser la place.

http://www.purebasic.fr/french/viewtopi ... 8&start=60

Pour contracter encore le vecteur de la première ligne nous ne prendrons que les différences entre colonnes contenant éventuellement des nombres premiers.
Le vecteur des différences entre colonnes ainsi créé peut servir pour passer d’un nombre à l’autre mais aussi pour déterminer l’ensemble des diviseurs.

Pour commencer il faut déterminer le choix d’un nombre susceptible de contenir un nombre premier.

Comme le vecteur des différences est cyclique. Il faut rechercher la première colonne susceptible de contenir un nombre premier
Exemple soit Nb_dep le premier nombre dont nous voulons savoir s’il est premier.

1) Il faut choisir un modulo= p_fact(13)= 30030 on peut choisir un autre p_fact 2 ou 3 ou 5 ou 7 ou 11 ou 13.
Pour utiliser les p-fact 17 et 19 il faudra utiliser le prg de génération du vecteur des différences car ces vecteurs sont trop longs pour être placés dans le prg ci-dessous.

2) prenons le reste de la division nb_rest= Nb_dep%modulo. Celui-ci correspond à une colonne de la matrice

3) Ce nombre doit être comparé à un numéro de colonne pour savoir ci celle-ci contient éventuellement un nombre premier. Si cette colonne ne contient pas de nombre premier nous prendrons la première colonne suivante contenant éventuellement un nombre premier C’est ce que j’ai appelé la synchronisation.

4) A partir de ce nombre ou de cette colonne on applique tous les diviseurs susceptibles d’être premiers en commençant par le premier nombre susceptible d’être premier après le dernier nombre premier utilisé dans p_fact ex : si p_fact(13) le premier nombre suivant 13 susceptible d’être premier est 17

5) Comme ce nombre est synchronisé avec la colonne de 1 nous passons de ce diviseur au diviseur suivant en additionnant la différence pour obtenir la prochaine colonne et ainsi de suite jusqu’à la fin du vecteur où nous reprenons l’indice à 1 jusqu’à ce qu’il ne reste plus de diviseur avec arrêt si diviseur> pow(nb_dep,0,5) la racine carré de nb_dep. Nous avons donc trouvé un nombre premier ou alors nous arrêtons les diviseurs si le reste de la division NB_dep%diviseur =0 c'est-à-dire que lun des diviseurs et un diviseur de Nb_dep donc Nb_dep n’est pas premier

6) Il faut maintenant incrémenter Nb_dep d’une colonne susceptible de contenir un nombre premier avec le vecteur des différences et en suite nous reprenons au 4)

Code : Tout sélectionner

; algorithme de recherche des nombres PREMIERS par zones 
; ATTENTION ENTRE 1E2-1E1 =90 entre 1E3-1E2=900 entre 1E4-1E3=9000 entre 1E12-1E11= 900000000000
; Le nombre 1 n'est pas par convention un nombre premier.
EnableExplicit
; DisableDebugger
structure divp 
  DIF.l
  i_ind.l
endstructure  
Structure DIV
  PREMDIV.l
  NBSEQ.l
  Array TDIF.l(2000000)
  array SDIF.L(2000000)
  ;   array prem.divp(600000)
EndStructure
Global nbs.l,NBSEQ.l,MODULO.l,result$,rest
Define SEQD.div
; 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

; Procedure choixdiv ( *EL.DIV )

Procedure choix_div ( *EL.DIV)
  Protected mess$, nb$, ELEM, ipas, i, i_prem
  ;********************************************* 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
  mess$=""
  SAISIE0:
  mess$+"p_fact=Filtre de réduction des diviseurs"
  
  If Len(mess$)>120
    MessageRequester("Erreur","Donnez p_fact avec  <= à  2 3 5 7 11 13 17 19 23"+#CR$+"Relancez le prg") ;
    End
  EndIf
  nb$=InputRequester(mess$,"Donnez p_fact <= à 2 3 5 7 11 13 17 19","13") ;
  If Len(nb$)>Len("13")
    Goto SAISIE0
  EndIf
  nbs=Val(nb$)
  If nbs<1 Or nbs>19
    Goto SAISIE0
  EndIf
  rest=nbs%30
  if rest=2 or rest=3 or rest=5 or rest=7 or rest=11 or rest=13 or rest=17 or rest=19 ;or rest=23 or rest=29
  else
    Goto SAISIE0
  endif 
  
  FINSAISIE0:
  ; ***************************  Chargement de la séquence à tester ******************************
  Select nbs
    Case 1,2
      modulo=2
      result$="2 "
      Restore DIV_02
    Case 3,4
      MODULO=6
      result$="2 3 "
      Restore DIV_03
    Case 5,6
      modulo=30
      result$="2 3 5 "
      Restore DIV_05
    Case 7 To 9
      modulo=210
      result$="2 3 5 7 "
      Restore DIV_07
    Case 10 To 11
      modulo=210*11
      result$="2 3 5 7 11 "
      Restore DIV_011
    Case 12 To 13
      modulo=210*11*13
      result$="2 3 5 7 11 13 "
      Restore DIV_013
    Case 14 To 17
;       messagerequester(" ATTENTION", " Pour utiliser le p_fact(17) ou p_fact(19)il faut générer le fichier DIV0_17.pb  ou DIV0_19.pb"+#CRLF$+" avec le prg GENERATEUR_DU_VECTEUR_DES_DIFFERENCES ")
;       End
      ;;; si vous avez généré le fichier DIV0_17.pb commentez les 2 lignes précédentes et decommentez la ligne  ;     IncludeFile "DIV0_17.pb"
      modulo=210*11*13*17
      result$="2 3 5 7 11 13 17 "
      Restore DIV_017
    Case 18 To 19
;       messagerequester(" ATTENTION", " Pour utiliser le p_fact(17) ou p_fact(19)il faut générer le fichier DIV0_17.pb  ou DIV0_19.pb"+#CRLF$+" avec le prg GENERATEUR_DU_VECTEUR_DES_DIFFERENCES ")
;       end
     ;;; si vous avez généré le fichier DIV0_19.pb commentez les 2 lignes précédentes et decommentez la ligne  ;     IncludeFile "DIV0_19.pb"

      modulo=210*11*13*17*19
      result$="2 3 5 7 11 13 17 19 "
      Restore DIV_019
      ;     Case 20 To 23  ; trop grand pour le bénéfice à en tirer
      ;       Restore DIV_023
      
  EndSelect
  Read.l *EL\PREMDIV
  i_prem=*EL\PREMDIV
  i=0
  *el\SDIF(0)=1
  Repeat
    Read.l ELEM
    If ELEM<>0
      
      *EL\TDIF(I+1)=elem
      *el\SDIF(I+1)=i_prem
      ;       *el\prem(i_prem)\i_ind=I+1
      ;       *el\prem(i_prem)\DIF=elem
      i_prem+elem
      ;        *EL\TDIF(I)=elem
      i+1
    EndIf
  Until ELEM=0
  *el\TDIF(0)=*EL\TDIF(I)
  
  *EL\NBSEQ=I
  NBSEQ=I
  ipas=0
  ;*************************************  Utilisation de la table TDIF ******************************
  ;   PREMDIV.l     NBSEQ.l
  ; L'exploitation de cette table est réalisée sur NBSEQ avec :
  ; de 1 à 8 avec le premier nombre PREMDIV
  ; ou de 0 à 7 avec le premier nombre si le reste de la division est 1 
  DataSection
    DIV_02:
    ;     IncludeFile "DIV0_2.pb"
    DATA.L  3,2,0 ;
                  ;; Modulo=2 Nb d'éléments dans vecteur=1 GAin=50%
    div_03:
    ;     IncludeFile "DIV0_3.pb"
    DATA.L  5,2,4,0 ;
                    ;; Modulo=6 Nb d'éléments dans vecteur=2 GAin=67%    
    DIV_05:
    ;     IncludeFile "DIV0_5.pb"
    DATA.L  7,4,2,4,2,4,6,2,6,0 ;
                                ;; Modulo=30 Nb d'éléments dans vecteur=8 GAin=73%
    DIV_07:
    ;     IncludeFile "DIV_7.pb"
    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 ;
                                                                                                                   ;; Modulo=210 Nb d'éléments dans vecteur=48 GAin=77%   
    div_011:
    ;     IncludeFile "DIV_11.pb"
    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 ;
     ;; Modulo=2310 Nb d'éléments dans vecteur=480 GAin=79%   
    
    ;***************************************************************************************************************************************************************************
    ;*********                   A partir de p_fact(13) sous div_013 le vecteur généré et trop important pour être placer ici                                       ************
    ;*********    pour générer le vecteur dans le même répertoire sous forme de fichier utiliser le prg GENERATEUR_DE_VECTEURS_DES_DIFFERENCES  pour 13 17 et 19    ************
    ;***************************************************************************************************************************************************************************
    
    div_013:
;     IncludeFile "DIV0_13.pb"
DATA.L  17,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,6,6,2,10,2,4,2,12,12,4,2,4,6,2,10,6,6,6,2,6,4,2,6,4,14,4,2,4,6,8,6,10,2,4,6,2,6,6,6,4,6,2,6,4,8,10,2,10,2,4,2,4,6,8,4,2,4,12,8,4,2,6,4,6,12,2,4,2,12
Data.L 6,4,6,6,6,2,6,10,2,4,6,2,6,6,4,2,10,2,10,2,4,6,6,2,6,6,4,6,8,6,4,2,6,4,6,8,4,2,6,4,8,6,4,8,4,6,8,10,2,10,2,6,4,2,4,2,10,2,10,2,4,2,4,14,4,2,4,6,6,2,6,4,8,10,8,4,2,4,6,8,6,4,6,6,6,2,6,6,4,2,4,6,2,10,2,4,2,10,2,10,2
Data.L 6,4,8,6,4,2,4,6,6,8,4,2,6,10,8,4,2,6,4,8,10,6,2,4,8,6,6,4,2,4,6,2,6,4,6,2,10,12,2,4,2,4,6,2,6,4,2,4,12,2,6,6,10,6,8,4,2,4,2,4,8,6,12,4,6,2,12,4,2,4,6,8,4,2,4,2,12,10,2,4,2,4,6,2,10,2,4,6,8,6,4,2,6,4,6,8,4,6,2,4,8
Data.L 6,4,6,2,4,6,2,6,6,4,6,6,8,6,4,2,10,2,10,2,4,2,10,2,6,4,2,10,6,2,6,4,2,6,4,6,8,6,4,2,12,10,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,10,6,2,6,4,12,6,8,6,4,2,4,8,6,4,6,2,4,6,8,6,6,4,6,2,6,4,2,4,2,10,12,2
Data.L 4,12,2,6,4,2,4,6,6,2,12,6,4,18,2,4,2,4,8,6,4,6,2,4,8,6,6,4,2,4,6,2,6,4,2,4,12,2,12,6,4,6,2,6,4,6,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,10,2,10,2,4,14,10,2,4,2,4,6,2,6,10,6,6,2,10,2,6,4,6,8,4,2,4,6,8,6
Data.L 10,2,4,6,2,6,6,4,2,4,6,2,6,4,2,6,10,2,10,6,2,4,6,8,4,2,4,12,2,6,4,2,6,4,6,12,2,4,2,4,8,6,4,6,2,10,2,6,10,6,6,2,6,4,2,4,2,10,2,12,4,6,6,2,12,4,6,6,2,6,4,2,6,4,14,4,2,6,4,8,6,4,6,2,4,6,8,6,6,10,2,6,4,6,2,10,2,10,2,4,2
Data.L 4,8,6,4,2,4,6,6,8,4,8,4,6,8,4,2,4,2,12,6,4,6,6,6,2,6,6,4,2,4,6,2,6,6,4,2,10,2,10,2,6,4,6,2,6,4,2,4,6,14,4,2,6,10,8,4,2,4,2,4,8,10,8,4,8,6,10,2,4,6,2,6,4,6,2,10,2,10,2,4,2,4,6,8,4,2,4,6,6,2,6,6,6,10,8,4,2,4,6,8,6
Data.L 4,8,4,6,2,6,6,4,2,4,6,12,2,4,2,10,2,10,2,4,2,4,8,10,2,4,6,8,6,4,2,6,4,6,8,4,8,4,8,6,4,6,2,4,6,2,6,6,4,6,6,2,6,6,4,2,10,12,2,4,2,4,6,2,6,4,2,16,2,6,4,2,10,6,8,4,2,4,2,12,6,10,2,4,6,2,12,4,2,4,8,6,4,2,4,2,12,10,6,2,4
Data.L 6,2,6,4,2,4,6,6,2,6,4,2,10,6,8,10,2,4,8,6,4,6,2,4,6,2,6,6,6,4,6,8,4,2,4,2,10,12,2,4,2,10,2,6,4,2,4,6,6,2,10,2,6,4,14,6,4,2,4,8,10,6,2,4,6,2,6,6,4,2,4,8,6,4,2,4,12,2,12,4,2,4,6,2,6,4,2,10,6,2,6,4,8,4,6,8,4,2,4,2,4
Data.L 14,4,6,2,10,8,6,4,2,4,6,2,10,2,4,2,12,10,2,4,6,6,2,6,4,6,6,6,2,6,6,6,4,6,12,2,4,6,8,6,10,2,4,8,6,6,4,2,4,6,2,6,4,2,6,10,2,10,2,6,4,6,8,4,6,12,2,6,4,2,6,4,6,12,2,4,2,4,14,4,6,2,4,6,2,6,10,2,10,2,6,4,2,4,12,2,10,2,4,6,6
Data.L 2,6,6,4,6,6,2,10,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,6,10,2,10,6,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,12,2,6,6,4,6,6,2,6,4,2,4,2,10,2,12,6,4,6,2,10,2,4,6,6,8,4,2,6,18,4,2,4,2,4,8,10,6
Data.L 2,4,8,6,6,6,4,6,2,6,4,6,2,10,2,10,2,4,2,4,6,2,6,4,2,4,6,6,8,6,6,4,6,8,4,2,4,2,12,6,4,12,6,2,6,6,4,2,4,6,8,6,4,2,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,8,4,6,2,6,10,6,6,2,6,6,4,2,10,2,10,2,4,2
Data.L 4,6,8,4,2,10,6,2,6,4,2,6,10,8,4,2,4,14,6,4,6,2,4,6,2,12,4,2,4,8,10,2,4,2,10,2,10,6,2,4,8,6,4,2,4,6,6,2,6,4,2,10,6,8,6,6,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,12,2,10,2,10,14,4,2,4,2,4,8,6,10
Data.L 2,4,6,2,12,4,2,4,6,2,6,4,2,4,14,12,4,2,4,6,2,6,4,2,4,6,6,2,6,4,2,6,4,6,8,4,6,2,4,14,4,6,2,10,2,6,6,4,2,4,6,12,2,4,2,12,10,2,4,2,10,2,6,4,6,6,6,2,6,4,2,6,4,6,8,6,4,6,8,16,2,4,6,2,6,6,4,2,4,8,6,4,2,6,10,2,10,2,4,2,4
Data.L 6,8,4,2,16,2,6,4,8,4,6,12,2,4,2,4,8,6,4,6,2,4,6,8,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,6,6,4,6,12,2,6,4,8,6,4,6,2,4,14,6,4,2,10,2,6,4,2,4,2,10,2,10,2,6,4,8,6,4,6,6,6,2,6,4,8,4,6,8,4,2,4,2,4,14,4,6
Data.L 6,6,2,6,6,4,2,10,2,6,4,2,4,12,2,10,2,6,4,6,2,6,6,4,6,6,12,2,6,10,8,4,2,4,2,4,8,10,6,2,4,8,6,6,4,2,4,6,2,6,4,8,10,2,10,6,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,10,2,6,6,4,6,6,8,4,2,4,2,10,2,12,4,2,4,6
Data.L 2,10,2,4,6,8,6,4,2,6,4,14,4,6,2,4,8,6,4,6,2,4,6,2,6,6,10,6,2,6,10,2,10,2,10,2,4,2,4,6,2,6,4,2,10,6,8,4,2,6,4,6,8,4,2,4,2,12,6,4,6,6,6,2,12,4,2,4,8,6,6,4,2,10,2,10,6,2,4,6,2,6,4,2,4,6,8,6,4,2,10,6,8,6,4,2,4,8,6,4,8
Data.L 4,6,2,6,12,4,6,2,6,4,2,4,2,10,12,2,4,2,10,8,4,2,4,6,6,2,10,2,6,18,4,2,4,6,8,6,4,6,2,4,6,2,6,6,4,2,4,6,2,10,2,4,12,2,12,4,2,4,8,6,4,2,4,6,6,2,6,4,2,6,4,6,8,4,2,6,4,14,4,6,2,10,2,6,6,4,2,4,6,2,10,2,4,2,22,2,4,2,4,6,2
Data.L 6,4,6,12,2,6,4,2,10,6,8,4,2,4,6,8,6,10,2,4,6,2,12,4,2,4,6,2,6,4,2,6,12,10,2,4,2,4,6,8,4,2,4,12,2,6,4,2,6,4,6,12,6,2,4,8,6,4,6,2,4,6,2,6,10,2,4,6,8,4,2,4,2,10,2,10,2,4,12,2,6,6,4,6,6,2,6,4,2,6,4,6,8,6,6,4,8,10,6,2,4
Data.L 6,8,6,4,2,12,6,4,2,4,2,10,2,10,2,4,2,4,8,6,4,2,10,6,2,6,4,8,4,6,8,4,2,4,2,4,8,6,4,6,6,6,8,6,4,2,4,6,2,6,4,2,4,2,10,2,10,2,10,6,2,6,4,2,4,6,6,8,6,6,10,12,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,6,4,6,2
Data.L 6,4,6,6,6,2,6,6,6,4,6,8,4,2,4,2,4,14,4,8,4,6,2,6,6,4,2,10,8,4,2,4,12,2,10,2,4,2,4,6,2,12,4,6,8,10,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,6,10,2,10,6,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
Data.L 2,10,2,12,4,6,8,6,4,2,4,2,10,2,16,2,4,6,2,10,2,4,6,6,2,6,4,2,10,14,6,4,2,4,8,6,4,6,2,4,6,2,6,6,6,4,6,2,6,4,6,2,10,12,2,4,2,10,2,6,4,2,4,6,6,12,2,6,4,14,4,2,4,2,12,6,4,6,6,6,2,6,6,4,2,4,6,2,6,6,4,12,2,12,4,2,4,6,2,6,4
Data.L 2,4,6,8,6,4,2,6,4,6,8,4,2,4,2,4,14,4,8,10,2,6,10,2,4,6,2,10,2,4,2,12,10,2,4,2,4,6,8,4,6,6,6,2,6,4,2,6,10,8,4,2,4,6,8,6,10,2,4,6,2,6,6,4,2,4,6,2,10,2,6,10,2,10,2,4,2,4,14,4,2,4,12,2,6,4,2,6,4,6,12,2,6,4,8,6,4,6,2,4,6
Data.L 2,6,10,2,4,6,2,6,4,2,4,2,10,12,2,4,6,6,2,6,6,4,12,2,6,4,2,10,6,8,4,2,6,4,8,6,10,2,4,6,14,4,2,10,2,6,4,2,4,2,12,10,2,4,2,4,8,6,4,2,4,6,6,2,6,4,8,4,6,8,4,6,2,4,8,6,4,6,6,6,2,6,6,4,2,4,6,8,4,2,4,2,10,2,10,2,6,10,2,6,4
Data.L 2,4,6,6,8,4,2,6,10,8,6,4,2,4,8,10,6,2,4,8,6,6,4,2,4,8,6,4,6,2,10,2,10,2,4,2,4,6,2,6,4,2,10,6,2,6,12,4,6,8,4,2,4,2,4,8,6,4,8,4,6,8,6,4,2,4,6,8,4,2,4,2,10,2,10,2,4,6,6,2,10,2,4,6,8,6,6,6,4,6,12,6,2,4,8,6,4,6,2,4,8
Data.L 6,6,4,6,6,2,6,6,4,2,10,2,10,2,6,4,6,2,6,4,12,6,2,6,4,2,6,4,6,8,4,2,4,2,18,4,6,2,4,6,2,12,4,2,12,6,4,2,4,12,2,10,6,2,4,6,2,6,6,4,6,6,2,10,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,6,10,12,6,2,10,2,6,4,2,4,6
Data.L 6,2,10,2,6,4,14,4,2,4,2,4,8,6,4,6,2,10,2,6,6,4,6,6,2,6,4,2,4,12,2,12,4,2,4,6,2,10,2,4,6,6,2,6,4,2,6,4,14,4,2,4,2,4,14,4,6,2,10,2,6,6,6,4,6,2,10,6,2,12,10,2,4,2,4,6,2,6,4,6,6,6,8,4,2,6,4,6,8,4,2,4,14,6,10,6,6,2,6,6,4
Data.L 2,4,6,2,6,6,6,10,2,10,2,4,2,4,6,8,4,2,4,14,6,4,2,6,4,6,12,2,4,2,4,8,6,4,8,4,6,2,6,10,2,4,6,2,6,4,2,4,2,10,2,10,2,4,6,6,8,6,4,6,6,2,6,4,2,6,10,8,4,2,10,8,6,4,6,2,4,6,8,6,4,2,10,2,10,2,4,2,10,2,10,2,4,2,4,8,6,4,2,4,6
Data.L 6,2,6,4,8,4,6,8,4,2,6,4,8,6,4,6,6,6,2,6,6,4,2,4,6,2,6,4,2,4,2,10,12,2,6,4,6,2,6,4,2,4,12,8,4,2,16,8,4,2,4,2,4,8,16,2,4,8,12,4,2,4,6,2,6,4,6,2,12,10,2,4,2,4,6,2,6,4,2,4,6,6,2,6,6,6,4,6,8,4,6,2,4,8,6,4,8,4,6,2,6
Data.L 6,4,2,4,6,8,4,2,4,2,10,2,10,2,4,2,10,2,10,2,4,6,8,6,4,2,6,4,6,8,10,2,4,8,10,6,2,4,6,2,6,6,4,6,8,6,6,4,2,10,2,10,2,4,2,4,6,2,6,4,2,10,6,2,6,4,8,4,6,8,4,2,4,2,12,6,4,6,2,4,6,14,4,2,4,8,6,4,2,4,2,10,2,10,6,6,6,2,6,4,2
Data.L 4,6,6,2,6,6,10,6,14,4,2,4,8,6,4,6,2,4,8,6,6,6,4,6,2,6,4,2,4,2,10,12,2,6,10,2,6,4,6,6,6,2,10,2,6,4,14,4,2,4,2,4,14,4,6,2,4,6,2,6,6,4,2,10,2,6,4,2,4,12,2,12,4,2,4,6,2,6,6,4,6,6,2,10,2,6,4,6,8,4,2,4,2,4,14,4,6,2,10,2,6
Data.L 6,4,2,4,6,2,10,2,6,12,10,6,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,10,2,6,6,4,6,6,2,6,4,2,6,10,2,12,4,2,4,6,12,2,4,12,2,6,4,2,6,4,18,2,4,2,4,8,6,4,6,2,4,6,2,6,12,4,6,2,6,4,6,2,10,2,10,2,4,6,6,2,6,6,4,6,6
Data.L 8,4,2,6,4,6,8,4,2,6,12,6,4,6,6,6,8,6,4,2,10,2,6,6,4,2,10,2,10,2,4,2,4,8,6,4,2,4,6,8,6,4,8,4,6,8,4,2,4,2,4,8,6,4,12,6,2,6,10,2,4,6,2,6,4,2,4,2,10,2,10,2,6,4,6,8,4,2,4,6,6,8,4,2,6,10,8,4,2,4,6,8,10,6,2,4,8,6,6,4,2
Data.L 4,6,2,10,6,2,10,2,10,2,4,2,4,8,6,4,2,4,6,6,2,6,6,6,4,6,8,4,2,6,4,8,6,4,8,4,6,2,6,6,4,2,4,6,8,4,2,4,2,10,12,2,4,2,4,6,2,10,2,4,14,6,4,2,10,6,8,4,6,2,4,8,6,10,2,4,6,2,12,4,6,6,2,6,6,4,2,12,10,2,4,2,4,6,2,6,4,2,10,6,2
Data.L 6,4,2,6,4,6,8,4,6,2,12,6,4,6,2,4,6,2,12,4,2,4,14,4,2,4,2,10,2,10,6,2,10,2,6,4,2,4,6,6,2,6,4,2,10,6,8,6,4,2,4,8,10,6,2,4,6,2,6,6,6,4,8,6,4,2,4,2,10,12,2,4,2,10,2,6,4,2,10,6,2,10,8,4,14,4,2,4,2,4,8,6,4,6,2,4,6,8,6,4,2
Data.L 4,6,2,6,4,2,4,12,2,12,4,6,6,2,6,4,2,4,6,6,2,6,6,6,4,6,12,2,4,2,4,14,4,6,2,12,6,6,4,2,4,6,2,10,2,4,2,12,10,2,6,4,6,2,6,4,6,6,6,2,6,4,2,6,4,6,8,4,2,4,6,14,10,2,4,6,2,6,6,4,2,10,2,6,4,2,16,2,10,2,4,2,4,6,8,6,4,12,2,10,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,6,10,2,10,6,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,10,8,6,4,12,2,6,4,2,4,2,10,2,12,4,2,4,8,10,2,4,6,6,2,6,4,8,4,14,4,2,4,2,4,8,6,4,6,6,6,2,6,6,6,4,6
Data.L 2,6,4,6,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,12,10,6,6,8,6,6,4,2,4,6,2,6,10,2,10,2,10,2,4,2,4,6,2,6,4,2,4,6,8,6,6,6,4,6,8,4,2,4,2,4,8,6,4,8,4,6,2,6,10,2,4,6,8,4,2,4,2,10,2,10,2,4,2,4,6,12,2,4,6,8,6
Data.L 4,2,6,10,8,4,6,6,8,6,4,6,2,4,6,2,6,6,4,6,6,2,12,4,2,10,2,10,2,4,2,4,8,6,4,2,10,6,2,6,4,2,6,4,6,8,4,2,6,12,6,4,6,2,4,6,2,12,4,2,4,8,6,4,2,4,2,10,12,6,2,4,6,2,6,4,2,4,12,2,6,4,2,10,6,8,6,4,2,4,8,6,10,2,4,6,2,12,6,4,6
Data.L 2,6,4,2,4,2,22,2,4,2,10,2,6,4,2,4,6,6,2,10,2,6,4,14,4,6,2,4,8,6,4,6,2,4,6,2,6,6,4,2,4,6,8,4,2,4,12,2,12,4,2,10,2,6,4,2,4,6,6,2,6,4,2,6,4,6,8,6,4,2,4,18,6,2,10,2,6,6,4,2,4,8,10,2,4,2,12,10,2,4,2,4,6,2,6,4,12,6,2,6,4
Data.L 8,4,6,8,4,2,4,6,8,6,10,2,4,6,8,6,4,2,4,6,2,6,4,2,6,10,2,10,2,4,6,6,8,4,2,4,12,2,6,6,6,4,6,12,2,4,2,4,8,6,4,6,2,4,8,6,10,2,4,6,2,6,4,2,4,2,10,2,10,2,10,6,2,6,10,6,6,2,6,4,2,6,4,6,8,4,2,6,4,14,4,6,2,4,6,8,6,4,2,10,2
Data.L 6,4,2,4,12,2,10,2,4,2,4,8,6,6,4,6,6,2,10,8,4,6,8,4,2,4,2,4,8,6,4,6,6,6,2,6,6,4,2,4,6,2,6,4,2,6,10,2,10,8,4,6,2,6,4,2,4,6,6,8,4,2,6,10,8,4,2,4,2,4,8,10,6,2,12,6,6,4,6,6,2,6,4,6,2,10,2,12,4,2,4,6,2,10,2,4,6,6,2,6,6
Data.L 6,4,14,4,2,4,2,4,8,6,4,8,4,6,2,6,6,6,4,6,8,4,6,2,10,2,10,2,4,2,4,6,2,10,2,4,6,14,4,2,6,4,6,8,4,6,2,12,6,4,6,6,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,8,6,4,2,6,4,6,8,4,2,4,2,12,6,4,8,4,6,2,16,2,4,8,6
Data.L 4,2,4,2,10,2,10,6,2,4,6,8,4,2,4,6,6,2,6,4,2,16,8,6,4,6,8,6,4,6,2,4,6,2,6,6,6,4,6,2,10,2,4,2,10,12,2,4,2,12,6,4,2,4,6,6,2,10,2,6,4,14,4,2,6,4,8,6,4,6,2,4,6,2,6,6,4,2,4,6,2,6,4,2,4,12,14,4,2,4,6,2,6,4,2,4,12,2,6,4,2
Data.L 10,6,8,4,2,4,2,4,14,10,2,10,2,12,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,6,6,8,6,10,2,4,6,2,6,6,4,2,4,6,8,4,2,6,10,2,10,2,4,2,10,8,4,2,4,12,2,6,4,2,6,4,6,14,4,2,4,8,10,6,2,4,6,2,6,10,2,4,8,6,4
Data.L 2,4,2,10,2,10,2,4,6,6,2,6,6,10,6,2,6,4,8,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,6,8,6,4,2,4,6,6,2,6,12,4,6,12,2,4,2,4,8,6,4,6,6,8,6,6,4,2,4,6,2,6,4,2,4,2,10,2,10,2,6,4,6,2,6,4,6,6,6,8,4,2
Data.L 6,10,8,4,2,4,2,4,18,6,2,4,8,6,6,4,2,10,2,6,4,6,12,2,10,2,4,2,4,6,2,6,6,4,6,6,2,12,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,6,10,2,10,6,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,10,2,6,6,4,6,6,2
Data.L 6,6,4,2,10,2,12,4,2,4,6,2,10,2,10,6,2,6,4,2,6,4,14,4,2,4,2,12,6,4,6,2,4,6,2,12,6,4,8,6,4,6,2,10,2,10,6,2,4,6,2,6,4,2,4,6,6,8,4,2,10,6,8,6,4,2,12,6,4,6,6,6,2,6,6,6,4,6,2,6,6,4,2,10,12,2,4,2,10,2,6,4,2,4,6,8,10,2,6,4,14
Data.L 4,2,4,2,4,8,6,4,8,4,6,2,6,10,2,4,6,2,6,4,2,4,12,2,12,4,2,4,6,8,4,2,4,6,6,2,6,4,2,6,10,8,4,2,4,6,14,4,6,2,10,2,6,6,4,2,4,6,2,10,2,4,2,12,10,2,4,2,4,8,6,4,6,6,6,2,6,4,2,6,4,6,8,4,2,10,8,6,10,2,4,6,2,6,6,4,2,4,6,2,6
Data.L 4,2,6,10,12,2,4,2,4,6,8,4,2,4,12,2,6,4,2,10,6,12,2,4,2,4,8,6,10,2,4,6,2,16,2,4,6,2,6,4,2,4,2,12,10,2,4,6,6,2,6,6,4,6,6,2,6,4,2,6,4,6,8,4,8,4,8,6,4,6,2,4,6,8,6,4,2,10,8,4,2,4,2,10,2,10,2,4,2,12,6,4,2,4,6,6,2,6,4,8,4
Data.L 6,8,6,4,2,4,8,10,6,6,6,2,6,6,4,2,4,8,6,4,2,4,2,10,2,10,2,6,4,6,2,6,4,2,10,6,8,4,8,10,8,4,2,4,2,4,8,10,6,2,4,14,6,4,2,4,6,2,6,4,6,2,10,2,10,2,4,6,6,2,6,4,2,4,6,6,2,6,6,6,4,6,12,2,4,2,4,8,6,4,8,4,8,6,6,4,2,4,6,8,4
Data.L 2,4,2,10,2,10,2,6,4,6,2,10,6,6,8,6,4,2,6,4,6,8,4,6,2,4,14,4,6,2,4,6,2,6,6,4,12,2,6,6,4,12,2,10,2,4,2,4,6,2,6,6,10,6,2,10,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,6,10,2,10,6,2,4,6,2,6,4,2,4,6,6,2,6,4,2,10
Data.L 6,8,6,4,2,4,8,6,4,6,2,10,2,6,6,10,6,2,6,4,2,4,2,10,14,4,2,10,2,10,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,6,4,6,2,6,4,6,12,2,12,4,2,4,6,2,6,4,2,4,6,6,8,4,2,6,4,6,8,4,2,4,2,18,4,6,12,2,6,6,4,2,4,6,2,12,4
Data.L 2,12,10,2,4,2,4,6,2,6,4,6,6,8,6,4,2,6,4,6,8,4,2,4,6,8,6,12,4,6,2,6,10,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,6,10,12,2,4,6,8,6,4,6,2,4,6,2,6,10,2,4,6,2,10,2,4,2,10,2,10,2,4,6,8,6,6,4,6,6,2,6,4,2,6,4,6
Data.L 8,4,2,6,4,8,6,4,6,2,4,6,8,6,4,2,10,2,6,4,2,4,2,10,12,2,4,2,4,8,6,4,2,4,12,2,6,4,12,6,8,4,2,4,2,4,8,6,10,6,6,2,12,4,2,4,6,2,6,4,2,4,2,12,10,2,6,4,6,2,6,4,2,4,6,6,8,4,2,6,10,8,4,6,2,4,8,10,6,2,4,8,6,6,4,2,4,6,8,4,6
Data.L 2,10,2,10,2,4,2,10,2,6,4,2,4,6,6,2,6,6,6,4,6,8,6,4,2,4,8,10,8,4,6,2,6,6,4,2,4,14,4,2,4,2,10,2,10,2,4,2,4,6,2,10,2,10,8,6,4,8,4,6,8,4,6,2,4,8,6,4,6,2,4,6,8,6,4,6,6,2,6,6,4,2,10,2,10,2,4,6,6,2,6,4,2,10,6,2,6,6,6,4,6
Data.L 12,2,4,2,12,6,4,6,2,4,8,12,4,2,4,8,6,4,2,4,2,10,2,10,8,4,6,2,6,4,6,6,6,2,6,4,2,10,6,8,6,4,2,4,14,4,6,2,4,6,2,6,6,6,10,2,6,4,2,4,12,12,2,4,2,10,2,6,6,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
Data.L 16,2,16,0 ;
  ;; Modulo=30030 Nb déléments dans vecteur=5760 GAin=81%
div_017:
    IncludeFile "DIV0_17.pb"
    ;; Modulo=510510 Nb d'éléments dans vecteur=92160 GAin=82%
div_019:
    IncludeFile "DIV0_19.pb"
    ;; Modulo=9699690 Nb d'éléments dans vecteur=1658880 GAin=83%
    
    ;     ;      div_023:
    ;     ;     IncludeFile "DIV0_23.pb"
    ;     ;; Modulo=223092870 Nb d'éléments dans vecteur=36495360 Gain=836%  il n'y a pas beaucoup de gain par rapport à p-fact(19)
  EndDataSection
EndProcedure
choix_div(SEQD)
define MIN.Q=1E12, mess$,nb$,pos, logmin, logmax, rmes,MIN_DEP.Q,ZONEP.Q

define MAX.Q=MIN+1E4
define ind, ind_dep,DIFF,divis.q,FLAGFIN,IND_NB,CENTM,DIVISM,IND_D, DIVIS$,MAXDIV.q,dep_time.q,cent,mins.q

mess$=""
SAISIE2:
mess$+"MIN Blanc +Zone à explorer avec MAX=MIN+1Ex  <= 1E2 +1E3 "

If Len(mess$)>250
  MessageRequester("Erreur","Donnez Min BLANC et Zone à explorer sous forme 1E3 +1E3 1E4 +1E4  1E9 +1E4 "+#CR$+"Relancez le prg") ;
  End
EndIf
nb$=ltrim(InputRequester(mess$,"MIN Blanc +Zone à explorer avec MAX=MIN+1Ex <= 1E2 +1E3 ","1E9 +1E4"));
pos=findstring(nb$," ")
MIN=vald(nb$)
ZONEP.Q=vald(ltrim(right(NB$,len(nb$)-pos)))
MAX=MIN+ZONEP

if MAX<=MIN or MIN<0 or MIN=>$7FFFFFFFFFFFFFFF ;;; = 9223372036854775807 valeur max positive en .q
  goto SAISIE2
endif 
logmin=log10(MIN)
logmax=log10(max-min)
if logmin+logmax>22
  rmes=messagerequester(" ATTENTION Temps très long","Oui=>continuez Non=>donnez autre zone",#PB_MessageRequester_YesNo)
  If Rmes = 6        ; le bouton Oui a été choisi (Resultat = 6)
  Else               ; le bouton Non a été choisi (Resultat = 7)
    goto SAISIE2
  EndIf
endif
MIN_DEP=MIN
if min=>Rest 
  result$=""
else 
  min=Rest 
endif  


; ******** sysnchronistion des Nombres à tester avec le vecteur des différences ***********
define restd.q=MIN%modulo 
for ind=0 to modulo 
  if restd<=seqd\SDIF(ind)
    ind_dep=ind 
    break 
  endif  
next   
DIFF=seqd\SDIF(ind_dep)-restd   
MIN+DIFF  
;************** Fin de sysnchronisation *************************************************
divis.q=SEQD\PREMDIV
flagfin=0
maxdiv.q=pow(min,0.5)
IND_NB=ind_dep
OpenConsole()

centm=min/100
divis$=str(min)+" "
divism=0
dep_time.q=ElapsedMilliseconds()
repeat 
  Ind_d=1
  
  while divis<=maxdiv; or FLAGFIN>0
    if MIN%divis =0 
      FLAGFIN+1 
      break
    else 
      divis+ SEQD\TDIF(Ind_d)
      Ind_d+1
      if Ind_d>SEQD\NBSEQ
        Ind_d=1;;; ;;; remise à 1 si le cycle des différences est atteint pour l'incrémentation des diviseurs susceptibles d'être premiers 
      endif    
    endif
  Wend
  
  if flagfin=0
 ;   debug _n(MIN)
    cent=min/100
    if centm<>cent 
      printn(result$)
      centm=cent 
         result$=str(min)+" " 
    else 
      result$+str(min)+" " 
    endif
  Else
    flagfin=0
  endif  
  
  MIN+ seqd\TDIF(ind_nb)
      ;************************************************ Recherche de la racine carré ***************************************************************
;    !FILD qword[v_MIN]
;    !FSQRT
;     ; !FISTTP dword [v_MAXDIV] ; 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 tout bon !!!!
;    !FISTP dword[v_MAXDIV] ; sans arrondi
;   maxdiv.q=pow(min,0.5)
 maxdiv.q=sqr(MIN)
  divis=SEQD\PREMDIV 
  ind_nb+1
  if ind_nb>SEQD\NBSEQ-1
    ind_nb=0  ;;; remise à zéro si le cycle des différences est atteint pour incrémentation des nombres susceptibles d'être premiers
  endif  
until min>max or min<0 ;;Si vous n'allez pas aux confins de la machine =$7FFFFFFFFFFFFFFF ;;; = 9223372036854775807 valeur max positive en ..q. 
;;                        Vous pouvez retirer (or min<0) ou dépassement de $7FFFFFFFFFFFFFFF
printn(result$)
Printn( "Nombre Minimal = "+FormatNumber(MIN_DEP, 0, " ", " ")+"  Nombre Maximal = "+FormatNumber(MAX, 0, " ", " "))
printn("Temps millisecondes ="+str(ElapsedMilliseconds()-dep_time))
input() 
CloseConsole()
; debug " "

; ***************** 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

Ce prg n’est pas optimisé. La seul optimisation est la racine carré de MIN réalisée en ASM qui me fait gagner 1 seconde sur 50 secondes soit 2% c’est peu.
Le point capital pour gagner de la vitesse est surtout la boucle des diviseurs répétée autant de fois qu’il y a de nombre entre MIN et MAX=MIN+zone à explorer par le nombre de diviseurs du nb_prem à la racine carré de Nb_dep. Boucle while à wend
On peut encore gagner du temps sur la boucle de nombres susceptibles d’être premiers
Boucle repeat à until min>max or min<0
Si vous n'allez pas aux confins de la machine =$7FFFFFFFFFFFFFFF = 9223372036854775807
valeur max positive en ..q. Vous pouvez retirer (or min<0) ou dépassement de $7FFFFFFFFFFFFFFF

Ici le prg GENERATEUR_DU_VECTEUR_DES_DIFFERENCES à placer dans le même répertoire que le prg précédent.

Code : Tout sélectionner

 Macro _q_t_
 	"

 EndMacro
 Macro _n (__n)
 _q_t_#__n#=_q_t_+Str(__n)+" "
 EndMacro
OpenConsole("Résultats partiel")
Dim T_MODULO.l(12)
Structure colonne
;   nb.q
	prem.a
	dif_prec.l
; 	Dif_act.l
EndStructure
; **************** Réalisation du vecteur modulo npp à partir d'une table des nombres premiers des 100 premiers nombres *********
;***** Choix du premier Nb premier pour lequel le vecteur modulo sera appliqué.
;***** pour éviter la génération d'un vesteur trop important nous limiterons ce choix aux 23 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
rest.l=nbs%30
if rest=2 or rest=3 or rest=5 or rest=7 or rest=11 or rest=13 or rest=17 or rest=19 or rest=23 or rest=29
else
  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-1
nbs=ELEM
Dim tcol.colonne(modulo+2)
;*** Recherche des colonnes ayant des nb premiers ***
tcol(0)\prem=2
tcol(1)\prem=2
Tdep.q=ElapsedMilliseconds()
For inb=2 To modulo+1
	For inbp=0 To nbprem
		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 *****
If CreateFile(0,"DIV0_"+Str(nbs)+".PB")         ; création d'un nouveau fichier texte...
  For inb=2 To modulo+1
;     tcol(inb)\nb=inb
		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
					If nb_prem%201=0
						PrintN(_n(NB_prem)+_n(prem_p)+_n(tcol(inb)\dif_prec)+_n(som_dif)+_n(ElapsedMilliseconds()-Tdep)+_n(lvecteur))
					EndIf
					If nb_prem%5=0  ; ici tous les =101*x  c'est avec 5 que l'on obtient le meilleur résultat
						vecteur$+Str(inb-prem_p)+#CRLF$
						lvecteur=Len(vecteur$)
						WriteString(0,vecteur$) ;
						vecteur$="Data.L "
					Else
						vecteur$+Str(inb-prem_p)+#CRLF$+"Data.L "
					EndIf
					
					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)
; 					tcol(prem_p)\Dif_act=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)
; 					tcol(prem_p)\Dif_act=inb-prem_p
					prem_p=inb
				EndIf
			EndIf
		EndIf
	Next
	;  tcol(modulo+2)\dif_prec=nb_prem+modulo-(modulo+1)
	NB_PREM+1
	tcol(modulo+2)\dif_prec=PREM_NB_PREM_AV-1
; 	tcol(1)\Dif_act=PREM_NB_PREM_AV-1
; 	tcol(1)\nb=1
	SOM_DIF+(PREM_NB_PREM_AV-1)
	rapportq.d=100.0*(modulo-Nb_prem)/modulo
	vecteur$+Str(PREM_NB_PREM_AV-1)+",0 ;"+#CRLF$+";; Modulo="+Str(modulo)+" Nb éléments dans vecteur="+Str(NB_prem)+" GAin="+str(rapportq)+"%"
	
	WriteString(0,vecteur$) ;
	CloseFile(0)            ; ferme le fichier précédemment ouvert et enregistre les données
	PrintN(_n(ElapsedMilliseconds()-Tdep))
	RAPPORT.D=modulo/NB_PREM
	MessageRequester("C'est tout bon","Somme des nb du vecteur="+_n(SOM_DIF)+#CRLF$+_n(modulo)+#CRLF$+"voir le fichier pour le détail du vecteur"+#CRLF$+"Fichier: "+GetCurrentDirectory()+"DIV_"+Str(nbs)+".PB"+#CRLF$+"Nomnre d'éléments dans le vecteur="+Str(NB_PREM)+" Rapport="+StrD(RAPPORT))
Else
	MessageRequester("Information","Impossible de créer le fichier! DIV_"+Str(nbs)+".PB")
EndIf

Input()
CloseConsole()

DataSection
	lab_pnbp:
	Data.l 2,3,5,7,11,13,17,19,23,29,31,0
EndDataSection

DataSection
  lab_pnbp2:
  Data.L   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
  DATA.L  101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199
  DATA.L  211,223,227,229,233,239,241,251,257,263,269,271,277,281,283,293
  DATA.L  307,311,313,317,331,337,347,349,353,359,367,373,379,383,389,397
  DATA.L  401,409,419,421,431,433,439,443,449,457,461,463,467,479,487,491,499
  DATA.L  503,509,521,523,541,547,557,563,569,571,577,587,593,599
  DATA.L  601,607,613,617,619,631,641,643,647,653,659,661,673,677,683,691
  DATA.L  701,709,719,727,733,739,743,751,757,761,769,773,787,797
  DATA.L  809,811,821,823,827,829,839,853,857,859,863,877,881,883,887
  DATA.L  907,911,919,929,937,941,947,953,967,971,977,983,991,997,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

Pour l’exemple voici un test réalisé aux limites des possibilités du calcul juste inférieur à MIN=$7FFFFFFFFFFFFFFF-1e4 avec une zone d’exploration de 100000
P_fact(19) en 64 bits sous win7

9223372036854765809 9223372036854765827
9223372036854765941
9223372036854766009 9223372036854766013 9223372036854766031 9223372036854766033 9223372036854766061
9223372036854766129 9223372036854766169 9223372036854766199
9223372036854766243 9223372036854766261
9223372036854766321 9223372036854766379 9223372036854766387
9223372036854766541
9223372036854766751 9223372036854766771 9223372036854766787
9223372036854766859
9223372036854766943 9223372036854766963 9223372036854766969
9223372036854767021 9223372036854767083 9223372036854767087
9223372036854767131 9223372036854767161
9223372036854767237 9223372036854767293
9223372036854767371 9223372036854767383
9223372036854767483
9223372036854767509
9223372036854767609 9223372036854767633
9223372036854767713
9223372036854767819 9223372036854767839 9223372036854767881
9223372036854767971
9223372036854768083
9223372036854768101 9223372036854768157
9223372036854768269
9223372036854768337 9223372036854768347
9223372036854768427 9223372036854768451 9223372036854768467 9223372036854768497
9223372036854768509 9223372036854768539
9223372036854768679
9223372036854768743 9223372036854768773
9223372036854768823 9223372036854768841
9223372036854768967 9223372036854768973
9223372036854769009 9223372036854769061 9223372036854769063 9223372036854769099
9223372036854769103 9223372036854769141 9223372036854769163
9223372036854769231 9223372036854769243 9223372036854769249 9223372036854769289
9223372036854769303 9223372036854769331 9223372036854769357 9223372036854769369
9223372036854769421 9223372036854769459
9223372036854769721 9223372036854769763 9223372036854769799
9223372036854769823
9223372036854769921 9223372036854769939
9223372036854770027
9223372036854770129 9223372036854770153
9223372036854770203 9223372036854770287
9223372036854770309 9223372036854770321 9223372036854770351
9223372036854770569 9223372036854770591
9223372036854770723 9223372036854770749
9223372036854770813
9223372036854770911 9223372036854770939
9223372036854771017 9223372036854771023 9223372036854771071
9223372036854771109 9223372036854771149
9223372036854771227 9223372036854771239
9223372036854771451 9223372036854771457 9223372036854771487
9223372036854771541 9223372036854771559 9223372036854771563 9223372036854771569 9223372036854771571
9223372036854771613 9223372036854771673 9223372036854771689
9223372036854771703 9223372036854771727 9223372036854771737 9223372036854771749 9223372036854771797
9223372036854771833 9223372036854771841 9223372036854771869
9223372036854771953 9223372036854771973 9223372036854771977 9223372036854771989
9223372036854772039 9223372036854772051 9223372036854772061
9223372036854772141 9223372036854772169
9223372036854772241 9223372036854772289
9223372036854772367
9223372036854772429 9223372036854772469
9223372036854772547
9223372036854772681
9223372036854772733
9223372036854772801 9223372036854772847
9223372036854772903 9223372036854772949 9223372036854772957 9223372036854772961
9223372036854773047 9223372036854773069
9223372036854773173
9223372036854773293
9223372036854773353
9223372036854773407 9223372036854773429 9223372036854773443 9223372036854773477 9223372036854773489
9223372036854773507 9223372036854773519 9223372036854773557 9223372036854773561
9223372036854773639
9223372036854773783
9223372036854773867 9223372036854773899
9223372036854773953 9223372036854773977 9223372036854773999
9223372036854774053
9223372036854774173 9223372036854774179 9223372036854774199
9223372036854774233 9223372036854774247 9223372036854774257 9223372036854774277
9223372036854774307 9223372036854774319 9223372036854774341
9223372036854774413 9223372036854774451 9223372036854774499
9223372036854774509 9223372036854774511 9223372036854774559 9223372036854774571 9223372036854774587
9223372036854774629 9223372036854774679
9223372036854774713 9223372036854774739 9223372036854774797
9223372036854774893
9223372036854774917 9223372036854774937 9223372036854774959
9223372036854775057 9223372036854775073 9223372036854775097
9223372036854775139 9223372036854775159 9223372036854775181
9223372036854775259 9223372036854775279 9223372036854775291
9223372036854775337 9223372036854775351 9223372036854775399
9223372036854775417 9223372036854775421 9223372036854775433
9223372036854775507 9223372036854775549
9223372036854775643
9223372036854775783
Nombre Minimal = 9 223 372 036 854 765 600 Nombre Maximal = 9 223 372 036 854 775 800
Temps millisecondes =1146078

soit 1146 secondes

A+

Merci PAPIPP ! Cette méthode semble très prometteuse. C'est sympa de voir que plusieurs personnes bossent sur le même problème, avec des méthodes différentes !

Voici aussi tant que j'y suis, un petit code (de test, pas très propre...) qui permet de chercher une formule d'approximation des nombres premiers, en fonction de 3 variables, et qui permet de comparer avec f(x) = suite des nombres premiers. Ça n'a rien de transcendant, mais si ça peut être utile à quelqu'un...

Comme on le voit, la suite suit à peu de choses près une exponentielle/logarithme, ce qui est normal en soi, puisque c'est un ensemble de nombres moins les nombres composés. D'ailleurs, je me demande si un nombre irrationnel a été trouvé avec les nombres premiers, à cheval entre les log et les exp, ça me semblerait logique, de même qu'avec les nombres composés...

Code : Tout sélectionner

;(c) djes 2016
;All rights reserved :) All rights reversed :)) Feel aaaaaalright !!!

#Max = 10000000

Define samples.i = 23*11

Define mrang_min.d = 0
Define mrang_max.d = 2
Define mrang_inc.d = 0.1

Define power_min.d = 0
Define power_max.d = 2
Define power_inc.d = 0.1

Define m_min.d = 1
Define m_max.d = 1
Define m_inc.d = 0

Macro formula
  rang * mrang * Log(rang * power) ; +m (not used here)
EndMacro
; Macro formula
;   rang * 1.078414 * Log(rang * 1.7008999 ) ;max gap 22113 on 100M
; EndMacro

;**********************************************

EnableExplicit
OpenConsole()

Macro _quote_
  "
EndMacro

;**********************************************
;- Primes lookup 
Define u.i, time.i, counter = 0, file
Define *pn.INTEGER, *sieve.INTEGER
Define lastpn.i


PrintN("*** Calculating primes ***")
PrintN("Range : 3-" + StrU(#Max))

*pn = AllocateMemory(#Max*8)
*sieve = AllocateMemory(#Max)
time = ElapsedMilliseconds()

u = 3 ;start after the "2"

EnableASM

mov rcx, u
mov r8, *sieve
mov r9, #Max
mov r10, r9
!cvtsi2sd xmm0, r9
!sqrtsd xmm1, xmm0
!cvtsd2si r9, xmm1
inc r9  ;Sqr(#Max) + 1
!LP:
;If BitNotSet(*sieve, u)
bt [r8], rcx
jc BITSET
;Sieve(*sieve, u)
mov rax, rcx
mul rax
!@@:
bts [r8], rax
add rax, rcx
add rax, rcx
cmp rax, r10
jl @b
!BITSET:
add rcx, 2 ;jump over even numbers
cmp rcx, r9
jl LP
DisableASM

time = ElapsedMilliseconds() - time
PrintN("Time elapsed : " + Str(time) + " ms")
time = ElapsedMilliseconds()

EnableASM
; How many pn ?
mov rcx, u
mov r8, *sieve
mov r9, *pn
mov r10, #Max
;add '1' manually ;)
mov qword [r9], 1
add r9, 8
!LP2:
;If BitSet(*sieve, u)
bt [r8], rcx
jc BITNOTSET
;Store pn number
mov [r9], rcx
add r9, 8
!BITNOTSET:
add rcx, 2
cmp rcx, r10
jl LP2

sub r9, *pn
shr r9, 3
mov counter, r9
DisableASM        

time = ElapsedMilliseconds() - time
PrintN("Time elapsed : " + Str(time) + " ms")
FreeMemory(*sieve)

lastpn = PeekI(*pn + counter * 8 - 8)
PrintN("Found " + counter + " prime numbers")

;**********************************************
;- Construct f(x) and adjust parameters
PrintN("*** Constructing f(x) and adjusting parameters ***")

OpenWindow(0, 0, 0, 800, 600, "VectorDrawing", #PB_Window_SystemMenu | #PB_Window_ScreenCentered)
CanvasGadget(0, 0, 0, 800, 600)

Define pn.d, x.d, y.d, uu.d, rang.d
Define mrang.d, power.d, m.d
Define e.d = 2.71828182845904523
Define gap.d, gapmax.d = 0
Define bestgapmax.d = 1000000000000
;Define gaps.d, gapsmax.d = 1000000000000
Define mmrang.d, mpower.d, mm.d
Define bestmrang.d, bestpower.d, bestm.d
Define *pn2.INTEGER, mrang2.d
Define widthRatio.d = 800 / counter
Define heightRatio.d = 600 / (lastpn)

Define counterRatio.d = counter / samples

Define Event

mrang = mrang_min
Repeat
  power = power_min
  Repeat
    m = m_min
    Repeat
      rang.d = 2
      uu = 0
      mrang2 = mrang
      u = 1
      gapmax = 0
      Repeat
        Event = WindowEvent()
        If Event = #PB_Event_CloseWindow
          Break 4
        EndIf
        *pn2 = *pn + u * 8
        pn = *pn2\i
        uu = formula
        gap = Abs(pn - uu)
        If gap > gapmax
          gapmax = gap
          mmrang = mrang
          mpower = power
          mm = m
        EndIf        
        ;        gaps = gaps + gap
        rang + counterRatio
        u + counterRatio
      Until u >= counter - 1
      ;      gaps / counter
      If gapmax < bestgapmax
        bestgapmax = gapmax
        bestmrang = mmrang
        bestpower = mpower
        bestm = mm
        PrintN("--------------------")
        PrintN("mrang : " + StrD(bestmrang))
        PrintN("power : " + StrD(bestpower))
        PrintN("m     : " + StrD(bestm))
        PrintN("Best sample gap " + StrD(bestgapmax))
        PrintN("-------------------")
        StartDrawing(CanvasOutput(0))
        Box(0, 0, 800, 600, $FFFFFF)
        StopDrawing()
        Gosub PNZOOM_CURVE
        Gosub FXZOOM_CURVE
        Gosub PN_FAST_CURVE
        Gosub FX_FAST_CURVE
      EndIf
      m + m_inc
    Until m >= m_max
    power + power_inc
  Until power >= power_max
  mrang + mrang_inc
  
  PrintN(StrD(mrang) + " / " +StrD(mrang_max)) 
  
Until mrang >= mrang_max

;**********************************************
;- Final drawing
PrintN("*** Please wait (CTRL/C to quit) ***")

mrang = bestmrang
power = bestpower
m     = bestm

StartDrawing(CanvasOutput(0))
Box(0, 0, 800, 600, $FFFFFF)
StopDrawing()
Gosub PNZOOM_CURVE
Gosub FXZOOM_CURVE
Gosub PN_CURVE
Gosub FX_CURVE

PrintN("*** Drawing f(x)-pn(x) ***")
Gosub FXminusPN_GRAPH

PrintN("")
PrintN("**************************")
PrintN("          RECAP")
PrintN("**************************")
PrintN("On a 1-" + Str(#Max) + " range (x)")
PrintN(" found " + Str(Counter) + " primes (y)")
PrintN("--------------------")
PrintN("Curves")
PrintN("Red : prime numbers")
PrintN("Green : your formula")
PrintN("Dark blue : prime numbers zoom on 1-1200 range")
PrintN("Light Blue : formula zoom")
PrintN("--------------------")
PrintN("Formula : " + _quote_#formula#_quote_)
PrintN("--------------------")
PrintN("mrang : " + StrD(bestmrang))
PrintN("power : " + StrD(bestpower))
PrintN("m     : " + StrD(bestm))
PrintN("Best final gap : " + StrD(gapmax)) ;final gap calculated from fx_curve
PrintN("-------------------")

PrintN("Press close to quit")

Repeat
  Event = WaitWindowEvent()
Until Event = #PB_Event_CloseWindow

CloseConsole()
End

;**********************************************
;- Main pn curve drawing
PN_CURVE:
StartVectorDrawing(CanvasVectorOutput(0))
MovePathCursor(0, 600)
rang.d = 2
uu = 0

For u = 1 To counter - 1
  pn = PeekI(*pn + u * 8)
  x = rang * widthRatio
  y = 600 - pn * heightRatio
  AddPathLine(x, y)
  rang + 1
Next u

VectorSourceColor(RGBA(255, 0, 0, 255))
StrokePath(1, #PB_Path_RoundCorner)
StopVectorDrawing()

Return

;**********************************************
;- approx f(x) curve drawing
FX_CURVE:
StartVectorDrawing(CanvasVectorOutput(0))
MovePathCursor(0, 600)
rang.d = 2
uu = 0
gapmax = 0

For u = 1 To counter - 1
  pn = PeekI(*pn + u * 8)
  uu = formula
  x = rang * widthRatio
  y = 600 - uu * heightRatio
  gap = pn - uu
  If Abs(gap)>gapmax
    gapmax = Abs(gap)
  EndIf
  AddPathLine(x, y)
  rang + 1
Next u

VectorSourceColor(RGBA(0, 255, 0, 255))
StrokePath(1, #PB_Path_RoundCorner)
StopVectorDrawing()

Return

;**********************************************
;- Main pn curve fast drawing
PN_FAST_CURVE:
StartVectorDrawing(CanvasVectorOutput(0))
MovePathCursor(0, 600)
rang.d = 2
uu = 0

u = 1
Repeat
  pn = PeekI(*pn + u * 8)
  x = rang * widthRatio
  y = 600 - pn * heightRatio
  AddPathLine(x, y)
  u + counterRatio
  rang + counterRatio
Until u >= counter - 1

VectorSourceColor(RGBA(255, 0, 0, 255))
StrokePath(1, #PB_Path_RoundCorner)
StopVectorDrawing()

Return

;**********************************************
;- approx f(x) curve fast drawing
FX_FAST_CURVE:
StartVectorDrawing(CanvasVectorOutput(0))
MovePathCursor(0, 600)
rang.d = 2
uu = 0

u = 1
Repeat
  pn = PeekI(*pn + u * 8)  
  uu = formula
  x = rang * widthRatio
  y = 600 - uu * heightRatio
  ;   gap = pn - uu
  ;   If Abs(gap)>gapmax
  ;     gapmax = Abs(gap)
  ;   EndIf
  AddPathLine(x, y)
  rang + counterRatio
  u + counterRatio
Until u >= counter - 1

VectorSourceColor(RGBA(0, 255, 0, 255))
StrokePath(1, #PB_Path_RoundCorner)
StopVectorDrawing()

Return

;**********************************************
;- Zoom on 1-1200 range pn curve drawing
PNZOOM_CURVE:
StartVectorDrawing(CanvasVectorOutput(0))
MovePathCursor(0, 600)
rang.d = 2
uu = 0

For u = 1 To 1200 - 1
  pn = PeekI(*pn + u * 8)
  uu = formula
  x = rang / 2
  y = 600 - pn / 20.0
  AddPathLine(x, y)
  rang + 1
Next u

VectorSourceColor(RGBA(0, 0, 255, 255))
StrokePath(1, #PB_Path_RoundCorner)
StopVectorDrawing()

Return

;**********************************************
;- Zoom on 1-1200 range f(x) curve drawing
FXZOOM_CURVE:
StartVectorDrawing(CanvasVectorOutput(0))
MovePathCursor(0, 600)
rang.d = 2
uu = 0

For u = 1 To 1200 - 1
  pn = PeekI(*pn + u * 8)
  uu = formula
  x = rang / 2
  y = 600 - uu / 20.0
  AddPathLine(x, y)
  rang + 1
Next u

VectorSourceColor(RGBA(0, 255, 255, 255))
StrokePath(1, #PB_Path_RoundCorner)

StopVectorDrawing()
Return

;**********************************************
;- f(x) - pn graph
FXminusPN_GRAPH:
StartVectorDrawing(CanvasVectorOutput(0))
MovePathCursor(0, 300)
rang.d = 2
uu = 0

For u = 1 To counter - 1
  pn = PeekI(*pn + u * 8)
  uu = pn - (formula)
  x = rang * widthRatio
  y = 300 + uu * 300 / gapmax
  AddPathLine(x, y)
  rang + 1
Next u

VectorSourceColor(RGBA(200, 255, 0, 255))
StrokePath(1, #PB_Path_RoundCorner)
StopVectorDrawing()
Return

;**********************************************
FILE:
file = CreateFile(#PB_Any, #PB_Compiler_FilePath + "primes-org.txt")
For u = 1 To counter - 1
  pn = PeekI(*pn + u * 8)
  uu = formula
  x = rang * widthRatio
  y = 600 - pn * heightRatio
  gap = pn - uu
  WriteStringN(file, StrU(rang) + ", " + StrU(pn) + ", " + StrD(uu)  + ", " + StrD(pn / rang) + ", " + StrD(gap))
  ; gaps = gaps + (Abs(gap))
  If Abs(gap)>gapmax
    gapmax = Abs(gap)
  EndIf
  rang + 1
Next u
WriteStringN(file, "Found " + counter + " prime numbers")
CloseFile(file)
Return

@PAPIPP

Merci pour ton code, ça commence à prendre forme, mais j'ai un peu de mal à jouer avec. Pour l'optimisation, dans l'immédiat je sais pas trop par quel bout le prendre.

Dans la même approche j'avais réfléchi à faire un dispositif pour préparer le filtre à base de p-factorielle et j'ai mis un bout de test au point pour montrer ici :

Code : Tout sélectionner

Procedure.i NextPrime(n.i)
  If n = 2
    ProcedureReturn 3
  ElseIf n < 2
    ProcedureReturn 2
  ElseIf n & 1 = 0
    n + 1
  Else
    n + 2
  EndIf
  Repeat
    dmax.i = Sqr(n)
    d.i = 3
    IsPrime.i = #True
    Repeat
      If n % d = 0
        IsPrime = #False
        Break
      EndIf
      d + 2
    Until d > dmax
    If IsPrime
      ProcedureReturn n
    EndIf
    n + 2
  Until n < 0 ; break on overflow
EndProcedure

Procedure.q GCD(u.q, v.q)
  If u = v
    ProcedureReturn u
  EndIf
  If u = 0
    ProcedureReturn v
  EndIf
  If v = 0
    ProcedureReturn u
  EndIf
  If u & 1 = 0
    If v & 1
      ProcedureReturn GCD(u >> 1, v)
    Else
      ProcedureReturn GCD(u >> 1, v >> 1) << 1
    EndIf
  EndIf
  If v & 1 = 0
    ProcedureReturn GCD(u, v >> 1)
  EndIf
  If u > v
    ProcedureReturn GCD((u -v) >> 1, v)
  EndIf
  ProcedureReturn GCD((v - u) >> 1, u)
EndProcedure

;
; générateur p-fact
;
Dim Primes.i(1000)
For i.i = 1 To 1000
  n.i = NextPrime(n)
  Primes(i) = n
Next

pfact.i = 1
pu.i = 1
For i.i = 1 To 6
  pfact * Primes(i)
  pu * (Primes(i) - 1)
  Debug "i = " + Str(i) + #TAB$ + "Primes(" + Str(i) + ") = " + Str(Primes(i)) + #TAB$ + "p-fact(" + Str(Primes(i)) + ") = " + Str(pfact) + #TAB$ + "pu = " + Str(pu)
  Cols.s = ""
  Gaps.s = ""
  First.i = 0
  For j.i = 1 To pfact - 1 Step 2
    gcd.i = GCD(pfact, j)
    If gcd = 1
      Cols + Str(j) + #TAB$
      If Not First
        First = j
      Else
        Gaps + Str(j - First) + #TAB$
        First = j
      EndIf
    EndIf
  Next
  Debug Cols
  Debug "------------------------"
  Debug Gaps
  Debug "========================"
Next


CallDebugger
End

Ce code est peut-être pas idéal ni digeste, je n'en ai pas l'idée précise, mais le fil rouge dans cela est le suivant :

Pour une valeur donnée de p-fact(px) avec px étant le x-ième premier en partant du début, on sort la liste des "colonnes" utiles du filtre. En fait ces colonnes utiles sont indicées par les valeurs impairs n'ayant pas de diviseur commun avec p-fact(px), d'où l'utilisation d'une procédure GCD (pgcd plus grand commun diviseur), permettant de dire, si la valeur de retour est un, que deux nombres n'ont pas de diviseur commun (à part 1, dont on se fiche éperduement).

Cela permet de déduire les valeurs utiles issues de p-fact(px), et d'en déduire indirectement les écarts pour construire le vecteur.

Il me semble qu'en utilisant une méthode plus ou moins comme ça, on doit pouvoir rendre le code plus paramétrique et que cela devrait permettre de se rapprocher d'une optimisation en profondeur.

J'ai fait tourner de diverses manières l'approche utilisant un vecteur construit comme cela, mais je ne parviens pas pas à en tirer un meilleur parti que ce que je fais en utilisant un crible simple.

En fait, le partitionnement mod p (p-fact) pose un problème récurrent dès qu'on dépasse p-fact(2), ce qui correspond à un crible sur les nombres impairs (comme tout le monde sait faire), c'est le problème de gestion de butée, ou de bornage. Il n'y a pas plus précis qu'un pointeur qui va de nmin à nmax, il n'y a pas plus embêtant qu'une collection de pointeurs qui n'avancent pas à la même vitesse. Dans le code qu'Ollivier avait montré initialement, ça tapait pas mal hors plage, et le coût pour gérer des pointeurs multiples qui ne peuvent pas être testés en parallèle (même en vectorisant, le test parallèle est virtuel et il implique un traitement individualisé), cela coûte un bras.

Le parcours d'une plage par compteurs successifs est d'un coût moins élevé et la seule optimisation que l'on peut lui faire encore serait de filtrer une partie des composites si on parvient à le faire sans frais importants (en termes d'instructions machine).

Pour bien vérifier l'efficacité d'un algorithme ou d'un autre (en matière de crible pour test de primalité), il faut essayer de compter le nombre de hits sur le tableau de nombres (et ceux qui tapent en dehors éventuellement). Moi j'en suis arrivé à faire à peu près n/3+n/5+n/7+n/11+n/13+n/19 .... +n/sqr(n) ce qui est le nombre le moins élevé connu actuellement (proche de 3n).

L'utilisation d'un mécanisme visant à paralléliser doit permettre de ne pas dépasser ce type de quantité pour s'assurer d'une meilleure efficacité.

En tout cas pour l'instant, en mettant ce qu'il faut pour borner et gérer les pointeurs en parallèle, je n'arrive pas à mieux que sans paralléliser, ni même seulement à aller aussi vite.

Dans mon code Primes Gaps (version du jour, pas celle postée en début de thread ici), si je lance une plage comme celle que tu as sorti en exemple, j'obtiens des temps plus courts, y compris en comptant la montée en mémoire d'une table des premiers à hauteur de racine(nmax), avec un nmax à 2^63-1 sur une plage 1e5. Ca tourne environ 8 fois plus vite sur mon PC, ce qui laisse supposer qu'après optimisation on doit arriver à peu près aux-mêmes temps. A vérifier ce que ça donnera au bout du compte.

J'ai quelques bricoles à terminer sur Primes Gaps (7.3 version du jour), avant de reposter la mise à jour. Il permettra de bien traiter les nombres sur 64 bits (j'avais mis une limite à 1e15 auparavant pour des questions de performances). J'y ai inclus quelques contrôles de cohérence permettant de faire une validation à priori des résultats (car à calculer des nombres aussi éloignés du quotidien, la question se pose toujours de savoir si il sont justes ou pas).

Mon programme n'a pas fait de progrès notable pour l'instant en termes de performances de calcul. J'ai pris soin de revérifier toutes les possibilités d'amélioration utilisant une représentation binaire du crible, mais rien d'efficace sur le temps de calcul. Le seul gain que j'ai obtenu est d'être passé d'un tableau Quad à un tableau Byte, ce qui prend moins de place, mais cela donne aussi un temps d'accès sensiblement plus rapide lors des passes de crible. A retenir.

@djes,

J'ai en projet d'intégrer des sorties graphiques pour étayer les résultats statistiques dans mon prog. J'ai pas eu le temps de m'y mettre sérieusement. Un des problèmes qui me titille, serait de trouver une manière de représenter de manière correcte des courbes sur lesquelles on pourrait zoomer, avec une résolution partielle si on affiche une partie large de la plage numérique ... mais c'est un vrai boulot à faire et je n'ai pas vraiment commencé à m'y mettre.

Bonjour à tous

Une erreur a été corrigée dans le programme de recherche des nombres premiers.

http://www.purebasic.fr/french/viewtopi ... &start=120

A+

Super PAPIPP. Merci pour la mise à jour.

Bonsoir.

Pour permettre d'avoir un point de contrôle précis et validé, j'ai croisé les données entre différentes sources, différents algorithmes utilisés et différentes machines sollicitées, et j'ai obtenu la liste des premiers de la plage 2^63-10000 à 2^63-1 qui est la suivante :

9223372036854765809
9223372036854765827
9223372036854765941
9223372036854766009
9223372036854766013
9223372036854766031
9223372036854766033
9223372036854766061
9223372036854766129
9223372036854766169
9223372036854766199
9223372036854766243
9223372036854766261
9223372036854766321
9223372036854766379
9223372036854766387
9223372036854766541
9223372036854766751
9223372036854766771
9223372036854766787
9223372036854766859
9223372036854766943
9223372036854766963
9223372036854766969
9223372036854767021
9223372036854767083
9223372036854767087
9223372036854767131
9223372036854767161
9223372036854767237
9223372036854767293
9223372036854767371
9223372036854767383
9223372036854767483
9223372036854767509
9223372036854767609
9223372036854767633
9223372036854767713
9223372036854767819
9223372036854767839
9223372036854767881
9223372036854767971
9223372036854768083
9223372036854768101
9223372036854768157
9223372036854768269
9223372036854768337
9223372036854768347
9223372036854768427
9223372036854768451
9223372036854768467
9223372036854768497
9223372036854768509
9223372036854768539
9223372036854768679
9223372036854768743
9223372036854768773
9223372036854768823
9223372036854768841
9223372036854768967
9223372036854768973
9223372036854769009
9223372036854769061
9223372036854769063
9223372036854769099
9223372036854769103
9223372036854769141
9223372036854769163
9223372036854769231
9223372036854769243
9223372036854769249
9223372036854769289
9223372036854769303
9223372036854769331
9223372036854769357
9223372036854769369
9223372036854769421
9223372036854769459
9223372036854769721
9223372036854769763
9223372036854769799
9223372036854769823
9223372036854769921
9223372036854769939
9223372036854770027
9223372036854770129
9223372036854770153
9223372036854770203
9223372036854770287
9223372036854770309
9223372036854770321
9223372036854770351
9223372036854770569
9223372036854770591
9223372036854770723
9223372036854770749
9223372036854770813
9223372036854770911
9223372036854770939
9223372036854771017
9223372036854771023
9223372036854771071
9223372036854771109
9223372036854771149
9223372036854771227
9223372036854771239
9223372036854771451
9223372036854771457
9223372036854771487
9223372036854771541
9223372036854771559
9223372036854771563
9223372036854771569
9223372036854771571
9223372036854771613
9223372036854771673
9223372036854771689
9223372036854771703
9223372036854771727
9223372036854771737
9223372036854771749
9223372036854771797
9223372036854771833
9223372036854771841
9223372036854771869
9223372036854771953
9223372036854771973
9223372036854771977
9223372036854771989
9223372036854772039
9223372036854772051
9223372036854772061
9223372036854772141
9223372036854772169
9223372036854772241
9223372036854772289
9223372036854772367
9223372036854772429
9223372036854772469
9223372036854772547
9223372036854772681
9223372036854772733
9223372036854772801
9223372036854772847
9223372036854772903
9223372036854772949
9223372036854772957
9223372036854772961
9223372036854773047
9223372036854773069
9223372036854773173
9223372036854773293
9223372036854773353
9223372036854773407
9223372036854773429
9223372036854773443
9223372036854773477
9223372036854773489
9223372036854773507
9223372036854773519
9223372036854773557
9223372036854773561
9223372036854773639
9223372036854773783
9223372036854773867
9223372036854773899
9223372036854773953
9223372036854773977
9223372036854773999
9223372036854774053
9223372036854774173
9223372036854774179
9223372036854774199
9223372036854774233
9223372036854774247
9223372036854774257
9223372036854774277
9223372036854774307
9223372036854774319
9223372036854774341
9223372036854774413
9223372036854774451
9223372036854774499
9223372036854774509
9223372036854774511
9223372036854774559
9223372036854774571
9223372036854774587
9223372036854774629
9223372036854774679
9223372036854774713
9223372036854774739
9223372036854774797
9223372036854774893
9223372036854774917
9223372036854774937
9223372036854774959
9223372036854775057
9223372036854775073
9223372036854775097
9223372036854775139
9223372036854775159
9223372036854775181
9223372036854775259
9223372036854775279
9223372036854775291
9223372036854775337
9223372036854775351
9223372036854775399
9223372036854775417
9223372036854775421
9223372036854775433
9223372036854775507
9223372036854775549
9223372036854775643
9223372036854775783

Cette liste contient 216 nombres premiers, et sauf observation contraire, je la retiens comme référence de test rapide pour les nombres les plus élevés représentés en entiers 64 bits (sinon j'ai des données exhaustives jusqu'à 1e12, et des données peu documentées au delà).

Bonjour à tous

Quelques explications sur mon prg

En 2014 je me suis attaqué à la décomposition d’un nombre Z=>0 et =<7FFFFFFFFFFFFFFF en facteurs premiers. Le seul pb que j’avais, était de trouver une suite redondante des diviseurs.
P_fact(x) me convenait parfaitement pour trouver les diviseurs > au nombre x utilisé dans p_fact(x)
Comme je connaissais les diviseurs =< à x il me fallait trouver les autres diviseurs jusqu'à sqr(Z) à décomposer.
p_fact(x)--modulo-----------------Nb_occurrences des différences
3__________6__________________________2
5__________30_________________________8
7__________210________________________48
11_________2310_______________________480
13_________30030______________________5760
17_________510510 _____________________92160
19_________9699690____________________1658880
23_________223092870__________________36495360

On voit qu’à partir de p_fact(13) le vecteur devient très important. Il faut donc réduire ce vecteur
En ne gardant que les colonnes susceptibles d’avoir des nombres premiers
Il suffit de connaitre les différences entre chaque colonne utile.

Ainsi par exemple pour p_fact(5)=30
Les colonnes 1 7 11 13 17 19 23 et 29 peuvent contenir des Nb premiers
00-01-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
----P----------------------P--------------P-------P-------------P------P--------------P---------------------P Les P doivent être sous les colonnes 1 7 11 13 17 19 23 29
Delta-------6----------------------4----------2----------4----------2---------4---------------6------------------et 2 pour revenir sur la colonne 1 le cycle est complet

Ce vecteur à pour origine la colonne 1 on peut en déduire les autres colonnes :
1+6=7 7+4=11 11+2=13 13+4=17 17+2=19 19+4=23 23+6=29 et enfin 29+2=31 31%30=1 nous sommes à nouveau sur la première colonne on peut donc continuer 31+6=37 37+4=41 etc..
A tout vecteur des différences il faut un numéro de colonne associé au premier nombre du vecteur
Ainsi le nombre 1 est associé au vecteur 6 4 2 4 2 4 6 2
Mais pour le premier diviseur susceptible d’être premier est avec p-fact(5) c'est le nombre 7 qui appartient à la 7em colonne donc pour garder la même cohérence il faut décaler le vecteur précédent d’un ripage de 1 nombre vers la gauche Donc 7 est associé au vecteur 4 2 4 2 4 6 2 et 6 pour revenir à l’origine ce qui nous donne :
7+4=11 11+2=13 13+4=17 17+2=19 19+4=23 23+6=29 29+2=31 et enfin 31+6=37 etc..
On a défini une récurrence pour trouver les diviseurs potentiels.

Code : Tout sélectionner

divis.q=SEQD\PREMDIV   ; Premier diviseur associé à l’indice ind_d=1
flagfin=0
maxdiv.q=pow(min,0.5)
IND_NB=ind_dep  ;;; indice à donner après synchronisation du nombre de départ
OpenConsole()

centm=min/100
dep_time.q=ElapsedMilliseconds()
repeat      ;;; début  de la boucle générale  des nombres à tester
  Ind_d=1 ;;; mise à 1 de l’indice à  l’origine  des diviseurs  
  
  while divis<=maxdiv; or FLAGFIN>0   ;;;; boucle de test des diviseurs 
    if MIN%divis =0 ; test pour savoir si le nombre MIN est premier ou pas 
      FLAGFIN+1 
      Break  ;; Sortie de la boucle pour tout nombre MIN qui n’est pas premier
    else 
      divis+ SEQD\TDIF(Ind_d)  ;;; incrémentation du diviseur en fonction de la colonne (Ind_d)  
      Ind_d+1  ;;; incrémentation de l’indice du vecteur pour le prochain diviseur
      if Ind_d>SEQD\NBSEQ;;; L’indice Ind_d dépasse le nombre de séquence  on revient à 1 pour les  diviseurs
        Ind_d=1  ;;; ;;; remise à 1 si le cycle des différences est atteint pour l'incrémentation des diviseurs susceptibles d'être premiers 
      endif    
    endif
  Wend    ;;; Fin de la boucle des diviseurs
….

etc….

Maintenant occupons nous des Nb à tester susceptibles d’être premiers et prenons le p_fact (5)
Delta------------------6---------------------4--------------2---------------4--------------2--------------4---------------------------6--------------------- 2
-------P-----------------------------P-----------------P---------P------------------- P--------P----------------- P-----------------------------P
000 001 002 003 004 005 006 007 008 009 010 011 012 013 014 015 016 017 018 019 020 021 022 023 024 025 026 027 028 029
030 031 032 033 034 035 036 037 038 039 040 041 042 043 044 045 046 047 048 049 050 051 052 053 054 055 056 057 058 059
060 061 062 063 064 065 066 067 068 069 070 071 072 073 074 075 076 077 078 079 080 081 082 083 084 085 086 087 088 089
090 091 092 093 094 095 096 097 098 099 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 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359
360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389
390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419
420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 437 438 439 440 441 442 443 444 445 446 447 448 449
450 451 452 453 454 455 456 457 458 459 460 461 462 463 464 465 466 467 468 469 470 471 472 473 474 475 476 477 478 479
480 481 482 483 484 485 486 487 488 489 490 491 492 493 494 495 496 497 498 499 500 501 502 503 504 505 506 507 508 509
510 511 512 513 514 515 516 517 518 519 520 521 522 523 524 525 526 527 528 529 530 531 532 533 534 535 536 537 538 539
540 541 542 543 544 545 546 547 548 549 550 551 552 553 554 555 556 557 558 559 560 561 562 563 564 565 566 567 568 569
570 571 572 573 574 575 576 577 578 579 580 581 582 583 584 585 586 587 588 589 590 591 592 593 594 595 596 597 598 599
600 601 602 603 604 605 606 607 608 609 610 611 612 613 614 615 616 617 618 619 620 621 622 623 624 625 626 627 628 629
630 631 632 633 634 635 636 637 638 639 640 641 642 643 644 645 646 647 648 649 650 651 652 653 654 655 656 657 658 659
660 661 662 663 664 665 666 667 668 669 670 671 672 673 674 675 676 677 678 679 680 681 682 683 684 685 686 687 688 689
690 691 692 693 694 695 696 697 698 699 700 701 702 703 704 705 706 707 708 709 710 711 712 713 714 715 716 717 718 719

ETC …
Le nombre à décomposer doit être supérieur au plus grand premier suivant qui forme le modulo produit des =2*3*5 =30
les colonnes qui ont une entête P sont les colonnes susceptibles de contenir des NB PREMIERS les autres ne peuvent en contenir.
Le premier nombre à tester est 7 dans la colonne 7.
Les NB PREMIERS pour lesquels les tests doivent être réalisés Sont les NB susceptibles d’être PREMIERS P en tête de colonne les autres tests sont inutiles.
Le vecteur récurrent des différences entre les colonnes susceptibles de contenir des NB premiers permet de passer d'un nombre à l'autre est 6 ,4, 2, 4, 2, 4, 6, 2, la somme des termes du vecteur doit être égale au modulo ou p_fact(X) ici p_fact(5)= à 30
le Nb de colonnes susceptibles de contenir des Nb premiers est 8 sur un total de 30.
On peut continuer avec cette méthode récurrente comme cela jusqu'à la limite que l'on désire.

Par exemple soit le nombre 600 nombre pris comme départ des nombres à tester.
1) recherche de la colonne 600%30 =0 nous sommes sur la 0em colonne qui ne contient aucun nombre premier.
2) La synchronisation consiste à partir d’ un vecteur des Numéros des colonnes utiles qui sont 1 7 11 13 17 19 23 29 de trouver le nombre qui est dans la prochaine colonne c’est à dire le 1. En effet le nombre 600 ce trouve dans la 0em colonne et le premier nombre susceptible d’être premier est dans le colonne 1 La différence de colonne 1-0 me donne le premier nombre à tester susceptible d’être premier 600+(1-0)=601
3) Maintenant il faut trouver le vecteur qui me fera passer à la colonne suivante C’est 6 1+6=7em colonne avec pour Nombre 601+6=607 et ainsi de suite +4, +2, +4, +2, +4, +6, + 2 pour la colonne 631%30 = 1er colonne ou 1 le vecteur est donc ci 6 ,4, 2, 4, 2, 4, 6, 2
4) Comme le vecteur des diviseurs est 4 2 4 2 4 6 2 et 6 pour finir le cycle et celui des Nombres susceptibles d’être premier est 6 ,4, 2, 4, 2, 4, 6, 2 on peu combiner les 2 vecteurs de la façon suivante avec indice origine 1 pour les diviseurs et indice de départ 0 pour les nb ~premiers avec pour chacun des cycle 8 occurrences.

|-------------------| pour les nombres à tester avec colonne trouvée après synchronisation
6--4—2—4—2—4—6—2-- 6
__|-----------------------| pour les diviseurs avec premier diviseur ici 7
0—1—2—3—4—5—6—7—8 Indice de la table limitée à 8 occurrences.

Il serait possible de n’avoir qu’un seul vecteur mais cette solution me convient, elle évite de placer trop de code dans une boucle très très utilisée ainsi avec p_fact(5) modulo 30 et 8 occurrences. Pour aller des nombres pow(2,63)-10000 à pow(2,63) 10000 nombres donc 10000/30=333,3 cycles de 8 occurrences chacune donc 2666,6 nombres à tester avec pour chaque nombre un nb de diviseurs limité par sqr(pow(2,63)-10000)= 3037000499,976 soit 8 divisions pour chaque cycle de 30 donc 8*3037000499,976/30=809866799,99 divisions pour un nombre à tester et donc pour 2666 nombres Ce qui nos donne 809866799,99*2666=2159104888782,97 au maximum de divisions.

Par contre certains nombres sont éliminés rapidement. En supposant qu’on utilise pour chaque nombre testé en moyenne la moitié des divisions c'est-à-dire 809866799,99/2=404933399,995 il nous reste en moyenne 404933399,995*2666=1079552444386,67 divisions à réaliser
CE QUI EST ENORME

Avec p_fact(19) nous avons un taux de 0,17102 donc 10000*0,17102= 1710 nombres à tester.
Et sqr(pow(2,63)-10000))*0,17102=516897485,095 divisions par nombre testé
Donc pour les 1710,2 nombres en moyenne *516897485,0959/2=441999039505,5240

En comparant les résultats obtenus avec f(p_fact(5))/f(p_fact(19)
Soit 1079552444391/441999039505,5240=2,44 fois moins de divisions

Il faut donc utiliser un p_fact() le plus grand possible ici p_fact(19) pour l’instant.

A+

@PAPIPP

Merci pour ton intervention.
Et si tu testais des produits de nombres, plutôt que des nombres simples?

Soit a et b, 2 nombres susceptibles d'être premiers :

n = a * b

Soit g le gap entre a et b, on a :

n = a * (a + g)

Tester les restes de division de n jusqu'à la racine quatrième de n.

?

Bonjour Ollivier

Très intéressant comme idée.

J’ai commencé l’analyse du Pb.

Et je vois 3 problèmes.

1) Si A=9E18 et si B=A+delta alors A*B dépasse la capacité de la machine
Donc cette méthode ne peut être utilisée que pour des nombres < SQR( POW(2,63))

2) Sous la condition définie précédemment si A et B sont premiers pas de pb le produit A(A+delta) n’aura pas de diviseur en limitant la recherche à SQR(SQR(A*B)) ou pow(A*B,0.25) on a divisé le nombre de divisions de la boucle des diviseurs pour un nombre en test par 2.
Remarque :
SQR(A) est peu différent de SQR(B) puisque delta varie de 2 à x+Delta (Delta >2) avec p_fact(x)
Donc pour gagner en vitesse on peut prendre SQR(B) comme limite supérieure des diviseurs avec B=A+delta avec SQR(B)>(SQR(SQR(A*B)).

3) Si l’un des nombre A ou B n’est pas premier ou si aucun n’est premier, difficile à priori de savoir si l’un ou l’autre ou les 2 ne sont pas premiers. Dans tous les cas le produit (A*B) aura un diviseur et je m’arrête au premier diviseur.; Il faudra alors tester les 2 nombres séparément.

Je pense que statistiquement on doit y gagner en vitesse pour un Nombre à tester < SQR( POW(2,63)) mais le code dans la boucle la plus sollicitée sera plus complexe.

Bonsoir.

Je suis justement en train de me triturer les neurones sur la question de résoudre avec brio les problèmes de modulo en overflow.

Précisément dans un certain nombre de cas on doit passer par un produit de quelque chose qui déborde des 2^63-1 et on a deux approches possibles : bigint ou traitement spécifique de dépassement.

J'ai beau faire des pieds et des mains pour arriver à intégrer du bigint (ou APN : any precision numbers), ça ne fait pas de bonnes choses en termes de performances, ce que je savais, mais là on va oublier pour l'instant.

L'autre solution étant de ruser pour traiter certaines opération qui débordent en s'arrangeant pour qu'elles ne débordent pas. Mais j'en suis pour mes frais à l'heure qu'il est. Quoique je ne baisse pas les bras.

Mon besoin court terme est de pouvoir régler la question récurrent dans les tests de primalité de la gestion d'un modulo tel que : (a * b) % m donne une réponse correcte lorsque le produit a * b est en dépassement de capacité.

La solution de base, un peu moins rapide, consiste à faire ((a % m) * (b % m)) % m, ce qui reste efficace sans passer par des chemins trop compliqués. Mais là où je dois me faire vieux, c'est que j'en suis à des cas où le produit des modulos arrive en débordement lui-même et j'ai un peu de mal à en venir à bout.

Quand j'aurai sorti ça, et après vérification, je vous montrerai une approche de test de primalité statistique, qui viendra s'ajouter à mes outils pour compléter les tests déterministes. Pour vous mettre en appétit, je travaille sur l'algorithme Miller-Rabin qui est quasi-déterministe sur la représentation 64 bits à condition de réussir à gérer les débordements de capacité en 64 bits dans les tests modulos justement.

Je ne sais pas si ça alimentera le reste, mais c'est joli sur le papier.

Bonjour fweil

Je vois que tu essaies de dépasser les limites de la machine

Et en particulier comment trouver le reste de A*B%M avec des nombres très grand

Voici ma démonstration pour essayer d’y arriver.Les lettres en minuscule sont des indices

Revenons à la division euclidienne.

A=MQa+Ra avec Ra<M
Nous aurons avec A*B=MQab+Rab avec Rab<M
Or B=A+D delta variant de 2 à une valeur < X dans p-fact(X)
A*B=A*(A+D)=MQad+Rad avec Rad<M
Ou A*(A+D)= (MQa+Ra)*(MQa+Ra+D) =>MQaMQa+MQaRa+MQaD+RaMQa+RaRa+RaD (2)
Pour identifier cette équation avec l’équation MQab+Rab avec Rab<M
Plaçons M en facteur dans l'équation (2)
(3) M(MQaQA)+QaRa+QaD+RaQa)+RaRa+RaD=A*B= MQab+Rab avec Rab<M

Identifions le reste Rab=RaRa+RaD mais ce reste doit être < M
Écrivons l’équation euclidienne si (RaRa+Rad) nest pas <M

RaRa+Rad peut s »écrire MQr+Rr=RaRa+Rad remplaçons cette équation dans (3) même si Qr=0 donc même si RaRa+Rad <M
M(MQaQA)+QaRa+QaD+RaQa+Qr)+Rr=A*B
Or Si A*B= MQad+Rad nous obtenons par identification que Rr=Rad CQFD
donc pour trouver le reste du produit de 2 nombres
Il nous faut rechercher le reste de la division RaRa+RaD par M
Donc le reste de la division de A par M A%M=Ra => Ra(Ra+D)%M=Rr=Rab

Exemple en prenant des nombres dont le produit est inférieur pow(2,63)-1 pour pouvoir vérifier.

Code : Tout sélectionner

Macro _q_t_ 
	" 
EndMacro 
Macro _n (__n) 
_q_t_#__n#=_q_t_+Str(__n)+" " 
EndMacro 
A.q=Pow(2,30)
D=0
B.q=A+D
M.q=9699690 ;; modulo p_fact(19) ave Delta D variant 2 à 14 
for D=0 to 14 step 2
   B=A+D
  Ra=A%M
  Qa=(A-Ra)/M
  AB.Q=A*B
  Rab.q=AB%M 
  ;;; cherchons maintenant le reste à partir des éléments Ra Qa M et Ra
  Rest_partiel.q=Ra*Ra+(Ra*D)
  Rr.q=Rest_partiel%M
  debug _n(Rab)+_n(Rr)
  ;B=A+D
 Next

A+

PureBasic

A propos de nombres premiers

Re: A propos de nombres premiers

Re: A propos de nombres premiers

Re: A propos de nombres premiers

Re: A propos de nombres premiers

Re: A propos de nombres premiers

Re: A propos de nombres premiers

Re: A propos de nombres premiers

Re: A propos de nombres premiers

Re: A propos de nombres premiers

Re: A propos de nombres premiers

Re: A propos de nombres premiers

Re: A propos de nombres premiers

Re: A propos de nombres premiers

Re: A propos de nombres premiers

Re: A propos de nombres premiers