Turbo nombres premiers

[Ollivier]

C'est un peu beaucoup, 738 mégaoctets, non ?

[manababel]

La taille dépend du nombre "num q"

(sauf erreur de ma part)
num = 1548586400 octets
738 Mo = (( num / 2) / 1024) / 1024

pour :
num = 15485864000
on utilise 7384 Mo ( 7 Go) de RAM
sans optimisation , l'utilisation de la mémoire serait double.

avec la méthode "BTS" que tu as postée, on divise ses résultats par 4

[Ollivier]

Bonjour manababel, merci pour ces précisions.

Et, si tu utilises la librairie de compression de données (fonctions RAM/RAM), et que tu inclues la compression dans ta chronométrie, quelles valeurs comparatives pourrais-tu obtenir (mémoire et durée) ?

[manababel]

Bonjour Ollivier,
Je n'y ai jamais pensé, ici, c'était de trouver la façon la plus raide de calculer un nombre premier.
Ici, on stocke tous les nombres premiers , et ca a ses limites.
Il y a d'autres méthodes pour calculer un nombre premier.
Je pense qu'il faut sélectionner la méthode qui 'convient' à ces besoins.
Tel Quel je ne sais pas à quoi peut bien servir se programme.

(ps : BiTSet est plus lent que mov)

[PAPIPP]

C'est bien c'est même très bien la vitesse mais c'est mieux si les résultats sont corrects.

les premiers prg donnaient des résultats OK.

Essai ici du prg qui liste les 1000 premiers nombres qui ne sont pas tous premiers.
Le prg threadé donne les mêmes résultats.

Code : Tout sélectionner

Define num.q = 1548586400
Define sqrnum.q = Sqr(num)+1
Dim PrimeFlags.b(num>>1)
 
mill1.q = ElapsedMilliseconds()
  
For i.q=3 To sqrnum Step 2
  
  If PrimeFlags(i>>1) = 0
    
    !mov r9,[a_PrimeFlags]
    !mov rdx,[v_i]
    
    !mov rcx,rdx
    !add rcx,rcx
    !boucle:
      !mov rbx,rcx
      !shr rbx,1
      !jnc xxx ; on ne gere pas les nombres paires
        !mov byte [r9+rbx],1
      !xxx:
      !add rcx,rdx
      !cmp rcx,[v_num]
    !jl boucle   

  EndIf  

  
Next


mill1 = ElapsedMilliseconds()-mill1

mill2.q = ElapsedMilliseconds() 

count=0
OpenConsole()
For x=0 To (num-1)>>1 Step 1
  If PrimeFlags(x) = 0
    count+1
    If count<1000
      PrintN(Str(x))
    EndIf  ; Debug (x*2)+1 = nombre premier
  EndIf 
Next

mill2 = ElapsedMilliseconds()-mill2

num_ko = (num/2)/1024
num_mo = num_ko/1024
num_go = num_mo/1024
;EnableDebugger
FreeArray(PrimeFlags())
t$="part 1 : "+StrD(mill1/1000.0)+" seconds" + Chr(13)
t$=t$+"part 2 : "+StrD(mill2/1000.0)+" seconds" + Chr(13)
t$=t$+"TOTAL : "+StrD((mill1+mill2)/1000.0)+" seconds" + Chr(13)
t$=t$+Str(count)+" trouvé" + Chr(13)
t$=t$+Str(num_ko) + " Ko" + Chr(13)
t$=t$+Str(num_mo) + " Mo" + Chr(13)
t$=t$+Str(num_Go) + " Go" + Chr(13)
PrintN("C'est  fini")
Input()
CloseConsole()
MessageRequester("Information",t$,#PB_MessageRequester_Ok)

A+

[Ollivier]

Bonjour Papipp,

content de te lire ! Es-tu en 32 bits, ou bien en X64 ?

[PAPIPP]

Bonjour Ollivier

Je suis en 64 BITS car le thread utilise des instructions 64 bits

A+

[Ollivier]

Et c'est quoi ton code en fait? Vu qu'il est présenté dans le contexte où tu "casses la baraque" à manababel ?

Je ne peux pas le tester, vu que RBX est non volatile...

[manababel]

Bonjour Papipp
pour afficher le bon résultat, remplace :
"PrintN(Str(x))" par "PrintN(Str((x*2)+1))"

Ollivier, il doit être possible de gagner de la place
la première partie du programme calcul tous les nombres qui ne sont pas premiers
la deuxième partie sélection que les nombres non testés, donc premièr
en fusionnent les deux, on doit pouvoir gagner de la place.

[Ollivier]

D'accord, mais toi aussi, tu affectes RBX sans le sauvegarder...

On ne peut affecter que RAX, RCX, RDX, R8 et R9. Les autres registres, il faut les sauver.

Après, moi, avec 700 mégaoctets, je trie 21 milliards de nombres naturels. Ça doit être plus lent certainement. Je tâcherai de poster un code...

[Ollivier]

Comme je n'ai pas beaucoup de temps à consacrer à la programmation, voici, dans le but d'être compris et vérifié, l'algo que je vais utiliser

L'astuce est d'optimiser à la p-factorielle 2*3*5 (en l'occurence, 30). Autrement dit, le tableau s() de quads (pour commencer simple) représente les nombres susceptibles d'être premiers par paquets de 8 quads (utilisés de manière gourmande en mémoire, comme booléens), appliqués aux 8 nombres susceptibles d'être premiers dans chaque trentaine.

Alors c'est gourmand en mémoire, mais c'est pour ne pas pondre un code stratosphérique à l'avenir qui soit difficile à expliquer. Un quad, c'est 64 bits, donc, par proportion pure et simple, utiliser des bits réduira de 64 fois le besoin en mémoire.

C'est aussi pour pouvoir être vérifié facilement, au cas où cet algo serait faux. J'insiste sur le fait que 2, 3 et 5 sont considérés comme nombres premiers sans que cet algo, ni ne le prouve, ni le stocke.

Evidemment, toute référence à d'autres code source est la bienvenue, n'ayant pas oublié les recherches de Papipp, ni celles, non plus de fweil, ni celles de djes, 3 personnes avec qui des discussions publiques à ce sujet ont eu lieu dans le passé.

Alors, je m'arrête à la p-factorielle 2*3*5, pour des raisons d'architecture du CPU. Mais cette architecture n'est absolument pas utilisée de manière optimale : par contre, une fois optimisée, il sera impossible à quiconque de l'optimiser à une p-factorielle supérieure (ex : 2*3*5*7).

Donc, il est aussi possible d'augmenter la p-factorielle à 2*3*5*7 mais... Je n'irai pas pondre une optimisation machine derrière ! Impossible... Vu comment celle-là sera pondue, ce sera aussi souple que la surface d'une étoile à neutrons... La seule optimisation faisable sera les AVX mais uniquement avec cette p-factorielle (2*3*5)...

En attendant, voici comment ça se présente :

Code : Tout sélectionner

#sMax = 1 << 22 - 1 ; ici c'est 22 que je fais varier pour rester autour d'une seule seconde de traitement (pas suffisamment de courant pour rester triturer le CPU 3 heures !)
sqrMax = Sqr((#sMax + 1) / 8 * 30) ; la racine... comme d'hab...
Dim s.I(#sMax) ; le crible...
s(0) = 1 ; on considère d'office que 1 (cellule numéro 0) est composite (1)
; mais ça sous-entends que toutes les autres cellules sont considérées non composites (primalité vraie, mais à prouver, comme Eratosthène s'exécutait)
Dim M.I(7) ; tableau des valeurs susceptibles de contenir des premiers dans une trentaine.
M(0) = 1 ; à l'exception de 0K+1, on testera donc 31, 61, 91, 121, 151, etc...
M(1) = 7 ; on testera 7, 37, 67, 97, 127, etc...
M(2) = 11 ; on testera 11, 41, 71, 101, 131, etc...
M(3) = 13 ; on testera 13, 43, 73, 103, 133, etc...
M(4) = 17 ; on testera 17, 47, 77, 107, 137, etc...
M(5) = 19 ; on testera 19, 49, 79, 109, 139, etc...
M(6) = 23 ; on testera 23, 53, 83, 113, 143, etc...
M(7) = 29 ; on testera 29, 59, 89, 119, 149, etc..

; Tous les autres nombres, exceptés 2, 3 et 5 ne seront pas testés officiellement et considérés, d'office multiple de 2, 3 ou 5, et ceci sera valable, quelque soit la trentaine, ainsi tous ces autres nombres (exceptés 2, 3 et 5) seront considérés composites.


K = 0 ; on commence par la trentaine entre 0 et 29.
i0 = 1 ; on pointe M(1) = 7 au départ, car pointer M(0) = 1, ce serait cribler tous les multiples de 1 donc déguelinguer la logique...

t0 = ElapsedMilliseconds() ; on regarde l'horloge

Repeat ; on démarre la boucle
  K30 = 30 * K ; on calcule la trentaine
  N = K30 + M(i0) ; on calcule le nombre N
  If s(8 * K + i0) = 0 ; si N est premier (pas criblé)...
    N2 = N * N ; on calcule son carré...
    If N2 >= (#sMax + 1) / 8 * 30 ; le carré est-il hors limite ?
      Break ; oui, on se casse
    EndIf
    Repeat ; non, alors on va cribler les multiples de ce nb premier
      K_30 = N2 / 30 ; on calcule à quelle trentaine est ce nombre...
      M_ = N2 % 30 ; on calcule son modulo 30
      For I = 0 To 7 ; On va chercher quel est, parmi les huit nombres susceptibles d'être premiers, si notre nombre correspond...
        If M_ = M(I) ; si on a une correspondance...
          s((8 * K_30) + I) = 1 ; ...alors on crible
          Break ; et on cesse de chercher d'autres correspondances
        EndIf
      Next
      N2 + N ; on va tenter, de cette manière donc, de cribler les multiples de N
    Until N2 >= (#sMax + 1) / 8 * 30 ; et on s'arrête quand on est hors limite.
  EndIf
  i0 + 1 ; on teste notre nombre suivant, susceptibles d'être premier...
  If i0 > 7 ; on a testé les huit ?
    i0 = 0 ; oui, on reprend le premier nombre (sans jeu de mots...)
    K + 1 ; et on passe à la trentaine suivante...
  EndIf
  Debug N ; ça c'est pour quiconque n'y croirait pas...
Until N > sqrMax ; et ça c'est au cas, coïncidence, la racine carré de la quantité de nombres à tester serait malheureusement située dans un gap envahi de nombres composites, et donc n'aurait pas déclenché la 1ère sécurité plus haut (le fabuleux "on se casse" précédemment décrit)
t1 = ElapsedMilliseconds() ; on regarde le chrono de l'horloge...

; et on affiche quantité et durée de notre algo dont on peut apparemment assortir de la palme du boulet d'or, tellement je n'ai méga rien optimisé...
MessageRequester(Str((#sMax + 1) / 8 * 30) + " nb testés", Str(t1 - t0) + " ms")

... Mais, pour quiconque a l'oeil, les apparences sont trompeuses.

[Ollivier]

Alors, si c'est plutôt bien compris, on va compliquer un peu le berzingue, avant de le transcrire en ASM. On va rajouter un index.

Vous avez vu i0 ? Il indexe le petit tableau des 8 nombres susceptibles d'être premier dans chaque trentaine.

Ce tableau, en ASM, a peu de chance d'exister : il sera remplacé par un seul nombre constant chatouillé des millions de fois par seconde par le CPU. En ASM, pas de Dim M(7), pas de liste de 8 nombres en début de code, pas de M(i0) pour récupérer l'un de ces huit nombres. Juste un seul grand nombre précis déplacé (anglais move) dans un seul registre.

Code : Tout sélectionner

! mov r13, $fee

pour remplacer Dim et une liste de départ.

Cette subtilité est importante à préciser, car c'est ce qui déroute en ASM : les repères classiques du Basic, du C, du Pascal, de JavaScript ou autres sont comme des voitures passées dans un compacteur : on a du mal à s'y retrouver dans le code ASM d'autrui, exactement comme déplier une voiture sortie d'un compacteur pour y retrouver le chèque que l'on aurait oublié dans ce qui était la boîte à gants...

Voici donc notre tableau, en ASM : il correspond aux huit gaps respectifs aux huit nombres, chacun par rapport au précédent. Ça se lit comme l'écriture arabe, de droite à gauche.

Code : Tout sélectionner

110 100 010 100 010 100 110 010 (binaire par 3)
6   4   2   4   2   4   6   2   (nos gaps)

1101 0001 0100 0101 0011 0010 (binaire par 4)
D    1    4    5    3    2

1110011001101101 (sans suffixe 0)
E66D

1100110011011011 (idem décalé pour être masqué)
CCDB

Ainsi, si le CPU les lit successivement, les additionne au fur et à mesure, à chaque pas, chaque somme cause le nombre listé.
Partons de 29

Code : Tout sélectionner

29+2 = 31
31+6 = 37
37+4 = 41
41+2 = 43
43+4 = 47
47+2 = 49
49+4 = 53
53+6 = 59

Idem si, comble des nombres premiers toujours positifs, nous partons du nombre négatif -1

Code : Tout sélectionner

-1+2 = 1
1+6 = 7
7+4 = 11
11+2 = 13
13+4 = 17
17+2 = 19
19+4 = 23
23+6 = 29

Ainsi, se dévoilent toujours, sans accès à la RAM, sans utilisation du cache, sans affectation de la pile, un petit tableau répétitif, n'usant principalement que d'une addition pour produire les huit nombres dont nous avons besoin pour tester, théoriquement jusqu'à l'infini les seuls nombres, modulo 30, susceptibles d'être premier.

Code : Tout sélectionner

! mov rax, $D14532

J'aurai pu être encore plus "brutal" en étalant chaque gaps sur 8 bits au lieu de 3. Il est fortement possible que la vitesse sur 8 bits par gap soit plus grande, mais la place est chère au sein d'un CPU. La construction de chacun des huit nombres se fait comme suit

Code : Tout sélectionner

! ror rax, 3
! or rdx, rax
! and rdx, 7
! add rcx, rdx

Et c'est en priant le saint pipe-line inauguré il y a 26 ans déjà, qu'user de 3 bits, au lieu de 8 ne génère pas de perte de temps.

Alors, parfois, l'utile et l'agréable se rejoignent : nous pouvons réduire à 2 bits par gaps, vu que ces derniers sont tous pairs et se terminant tous par le "suffixe" 0. Ainsi, même le pipe-line va se reposer :

Code : Tout sélectionner

; version quasi-finale de notre tableau Dim M(7) des gaps de susceptibles premier de modulo 30
! mov eax, $E66D
! rol eax, 1
redo:
! mov dl, al
! and dl, 6
! add rcx, dl
! ror eax, 2
! jmp l_redo

On peut juste s'épargner d'une opération par décalage initiale de notre constante :

Code : Tout sélectionner

; version finale
! mov eax, $CCDB
redo:
! mov dl, al
! and dl, 6
! ror eax, 2 ; anticipation pour pipe-line rax/rcx/rdx
! add rcx, dl
! jmp l_redo ; saut ultérieurement conditionnel

Si RCX = 1 au départ (erreur de signe corrigée), il prendra les valeurs successives suivantes :

Code : Tout sélectionner

1
7
11
13
17
19
23
29
31
37
41
43
47
49
53
59
61
67
etc... jusquà l'infini

[PAPIPP]

Merci Manababel

J’ai pondu un prg de décomposition d’un nombre <=2E64-2
Et ensuite j’ai travaillé avec ollivier fweil et djes sur un prg de recherche des Nb premiers

Ce qui était recherché à l’époque c’était de déterminer les nb premiers entre deux bornes dans les limites de la machine en 32 bits donc pour tout nombre <= 2E64-2

Comme je le démontre ci-dessous il existe une relation entre les colonnes susceptibles de contenir des nb premiers c’est ce que j’appelle différence cyclique et il existe dans une même colonne une relation entre les différents nombre de la forme :
N = N° colonne + modulo*K le modulo est le résultat de p-factoriel
A l’époque je n’ai utilisé que la relation entre les colonnes susceptibles de contenir des nb premiers.

Alors que manababel utilise la relation dans une même colonne n=1+2K avec k= 0 1 2 3 etc dans la matrice à 2 colonnes (voir démo ci-dessous).


Voici mes phases de réflexion théoriques

En plaçant les nombres dans une matrice en choisissant le nombre de colonnes
Par exemple avec 2 colonnes
__0___----1---
...2.......3
...4.......5
...6.......7
...8.......9
Etc…
On voit qu’il n’y aura aucun nb premier dans la colonne 0 il n’y a que des nombres paires.
Gain ½= 50%

Les nombres dans la colonne 1 suivent l’équation N=1+2K avec k= 0 1 2 3 4 etc

En prenant la matrice avec 10 colonnes
___0__---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

Les nb premiers sont dans les colonnes 1 3 7 9 gain 6/10=60% mieux que la matrice à 2 colonnes
Dans une colonne N = N° colonne +10K avec k=0 1 2 3 4 etc
Un avantage de placer les nombres en matrice avec des colonnes où l’on ne trouvera jamais de nb premiers c’est que les différences entre les colonnes susceptibles d’avoir des nb premiers sont toujours cycliques et constantes
Les différences sont pour la matrice à 10 colonnes 2 4 2 2
Imaginons que nous avons trouvé un nb premier dans la colonne des 3 il suffit d’ajouter 4 pour être dans la colonne des 7 et ainsi de suite.

Afin de minimiser les colonnes susceptibles d’avoir des nb premiers essayons de construire une matrice avec 2 et 3 les deux premiers nb premier
Avec p_factoriel 2*3=6 soit n un nombre quelconque il appartient à la colonne n%6 c'est le reste de la division euclidienne par 6

N° colonne=N % 6 et N° ligne = (N / 6)+1

__0__---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

Or des têtes de colonnes 2 et 3 On ne peut trouver des nb premiers que dans les colonnes 1 et 5 soit un gain de 4/6=66,66%
On peut remarquer que les colonnes qui peuvent avoir des nb premiers sont la colonne du nouveau nb premier 5 et la toujours présente colonne 1 et ceci sera toujours vrai avec n'importe quel P-factoriel
4 est la différence entre la colonne 1 et la colonne 5 et 2 est la différence entre la colonne 5 est la colonne 1
Avec un cycle de différences 4 2 prenons 19 nb premier le prochain sera peut-être dans la colonne 1+4=5 et 19+4=23 gagné


Et dans une colonne N= N° colonne + 6K
Donc pour la colonne 1 N=1+6K et pour la colonne 5 N=5+6K
On peut voir ici une solution pour diminuer non seulement le temps d’exécution mais aussi la place utilisée dans les 2 tables avec pour relation :
Colonne 1 N=1+6K dans la première table
Colonne 5 N=5+6K dans la deuxième table


Et la relation horizontale avec les différences cycliques 4 2


avec p_factoriel 2*3*5=30

il y aura 30 colonnes dont les nombres ont la forme nombre = N°colonne+30K avec k=0,1,2,3...n
La colonne 0 pas nb premier K*30 toujours divisible par 2 3 5
Les colonnes 1 7 11 13 17 19 23 29 peuvent avoir des nb premiers
les autres colonnes non donc 22 colonnes sur 30 gain 22/30= 73,33%
les colonnes 7 11 13 17 19 23 29 qui sont en tête des colonnes sont les nouveaux nb premiers et toujours la fameuse colonne 1
Différences cyclique entre les colonnes 6 4 2 4 2 4 6 2
et le N° colonne= N % 30 et N° ligne = (N / 30)+1


Pour voir les résultats de ces réflexions allez

https://www.purebasic.fr/french/viewtop ... on#p188886

et

https://www.purebasic.fr/french/viewtop ... 89#p188289
*
A+

[Ollivier]

(Edité : oups... PAPIPP, je n'avais pas vu ta dernière réponse, je vais lire ça de ce pas ! En attendant, un ajout ci-dessous)

Bon... Je ne devais pas être réveillé pour balancer une constante erronée : c'est $F336 la bonne constante.
Mais on verra plus tard : autant rester encore un peu en pureBasic pour rajouter une petite optimisation purement mathématique et pas du tout technologique.

Alors mathématiquement, une chose sympa à savoir c'est ceci :
x % N = (x^K) % N

Traduction : Soit N, un nombre strictement supérieur à 1.
Et puis x, un nombre positif à étudier.
Quelque soit l'élévation de la puissance de x, son modulo N reste le même, soit : x % N.

(Mode confession ON)
(Ajouté ultérieurement) Je me suis foulé légèrement la cheville sur un trottoir après avoir posté ce message, en me disant que c'était bizarre que 7 modulo 10 faisait 7, tandis que (7*7) modulo 10 faisait 9 comme le neuf de 49. Alors, désolé, je ne me l'explique pas : en suivant la logique d'Eratosthène, si je constate 7 premier, alors je suis sensé cribler 7*2, puis 7*3, etc... Mais, moi ça fait des années qu'Eratosthène, je l'aime bien mais je crible 7*7, 7*8, 7*9, etc... Et le gap entre 7 et 11 donc 4, je l'honore, je le considère, donc je crible 7*(7) puis 7*7+(7*4) et non pas 7*7+7 puis 7*7+7+7 etc... Je fais une homothétie des gaps qui entourent le nombre premier P constaté, homothétie de gaps de facteur P à partir de P*P. Voilà. Donc, désolé pour cette fausseteté mathématique du modulo plus haut : j'ai confondu honteusement le modulo et le gap entre deux nombres premiers successifs.

Et encore, je fais cette homothétie, modulo 30. C'est à dire que tous les 30P après P*P, je reprends au gap entre P et Psuivant. Je pourrai faire une homothétie dite parfaite, mais, dans ce cas :
1) je ne peux cribler qu'en fonction de ma recherche.
2) je dois donc synchroniser mon criblage en fonction de ma recherche ce qui empêcherait de désolidariser en 2 threads distincts le criblage et la recherche.

Encore désolé pour la bévue maths !!
(mode confession OFF)


On verra qu'en ASM, ça peut être pratique.

En attendant, si un modulo reste semblable, malgré une élévation au carré, cela signifie que les gaps autour d'un premier seront aussi utiles autour de ce premier élevé au carré, pour cribler plus vite.

Donc, action : (toujours dans le même code-boulet pleins de multiplications et de divisions)

Code : Tout sélectionner

#sMax = 1 << 24 - 1 ; ici, je passe de 22 à 24 pour la même durée environ
sqrMax = Sqr((#sMax + 1) / 8 * 30)
Dim s.a(#sMax) ; le crible... je suis contraint de passer des quads aux octets
s(0) = 1
Dim M.I(7) ; tableau des valeurs susceptibles de contenir des premiers dans une trentaine.
M(0) = 1 ; à l'exception de 0K+1, on testera donc 31, 61, 91, 121, 151, etc...
M(1) = 7 ; on testera 7, 37, 67, 97, 127, etc...
M(2) = 11 ; on testera 11, 41, 71, 101, 131, etc...
M(3) = 13 ; on testera 13, 43, 73, 103, 133, etc...
M(4) = 17 ; on testera 17, 47, 77, 107, 137, etc...
M(5) = 19 ; on testera 19, 49, 79, 109, 139, etc...
M(6) = 23 ; on testera 23, 53, 83, 113, 143, etc...
M(7) = 29 ; on testera 29, 59, 89, 119, 149, etc...
Dim gap.I(7)
gap(0) = 6
gap(1) = 4
gap(2) = 2
gap(3) = 4
gap(4) = 2
gap(5) = 4
gap(6) = 6
gap(7) = 2

K = 0 ; on commence par la trentaine entre 0 et 29.
i0 = 1

t0 = ElapsedMilliseconds()

Repeat ; on démarre la boucle
  K30 = 30 * K
  N = K30 + M(i0)
  If s(8 * K + i0) = 0 ; si N est premier (pas criblé)...
    N2 = N * N ; on calcule son carré...
    If N2 >= (#sMax + 1) / 8 * 30 ; le carré est-il hors limite ?
      Break ; oui, on se casse
    EndIf
    i1 = i0 ; >>> NOUVEAU <<< on dupplique l'index
    Repeat ; non, alors on va cribler les multiples de ce nb premier
      K_30 = N2 / 30 ; on calcule à quelle trentaine est ce nombre...
      M_ = N2 % 30 ; on calcule son modulo 30
      For I = 0 To 7 ; On va chercher quel est, parmi les huit nombres susceptibles d'être premiers, si notre nombre correspond...
        If M_ = M(I) ; si on a une correspondance...
          s((8 * K_30) + I) = 1 ; ...alors on crible
          Break ; et on cesse de chercher d'autres correspondances
        EndIf
      Next
      ;(((N2 + N ; on va tenter, de cette manière donc, de cribler les multiples de N)))
      N2 + N * gap(i1) ; on crible désormais plus intelligemment
      i1 + 1
      i1 & 7
    Until N2 >= (#sMax + 1) / 8 * 30 ; et on s'arrête quand on est hors limite.
  EndIf
  i0 + 1 ; on teste notre nombre suivant, susceptibles d'être premier...
  If i0 > 7 ; on a testé les huit ?
    i0 = 0 ; oui, on reprend le premier nombre (sans jeu de mots...)
    K + 1 ; et on passe à la trentaine suivante...
  EndIf
  Debug N ; ça c'est pour quiconque n'y croirait pas...
Until N > sqrMax
t1 = ElapsedMilliseconds() ; on regarde le chrono de l'horloge...
Delay(1) ; alors, celui-là, j'ai rien compris : stabilise la durée de l'algo

; Je rajoute ceci pour que PAPIPP ou quiconque casse la baraque si je me trompe...
For I = 0 to #sMax
  If s(I) = 0
    P + 1
  EndIf
Next

; et on affiche quantité et durée de notre algo dont on peut apparemment assortir de la palme du boulet d'or, tellement je n'ai méga rien optimisé... Technologiquement...
MessageRequester(Str((#sMax + 1) / 8 * 30) + " nb testés", Str(t1 - t0) + " ms" + Chr(10) + Str(P) + " nbs 1ers")

[Ollivier]

Bon... Là encore, je prends le code précédent et je le modifie légèrement. Etape par étape. Cette fois-ci, pas d'accélération : on va juste gagner les 7/8 ièmes de la mémoire que je gaspillais, on passe au bit, plus qu'à l'octet.

Code : Tout sélectionner

#P2 = 24 ; on garde notre constante d'échelle pour régler facilement l'algo à une seule seconde d'exécution.
#sMax = 1 << (#P2 - 3) - 1 ; ici, j'adapte le facteur 8 (avec -3, car 2^3=8)

Macro sGet(K0, M0) ; pour lire le crible
  ((s(K0) >> M0) & 1)
EndMacro

Macro sSet(K0, M0) ; pour cribler
  s(K0) | (1 << M0)
EndMacro

Define.I sqrMax = Sqr((#sMax + 1) * 30) ; adapté
Dim s.a(#sMax) ; le crible...
s(0) = 1 ; réglage du 1 comme composite...
Dim M.I(7)
M(0) = 1
M(1) = 7
M(2) = 11
M(3) = 13
M(4) = 17
M(5) = 19
M(6) = 23
M(7) = 29
Dim gap.I(7)
gap(0) = 6
gap(1) = 4
gap(2) = 2
gap(3) = 4
gap(4) = 2
gap(5) = 4
gap(6) = 6
gap(7) = 2

K = 0
i0 = 1

t0 = ElapsedMilliseconds()

Repeat
  K30 = 30 * K
  N = K30 + M(i0)
  If sGet(K, i0) = 0 ; adapté
    N2 = N * N
    If N2 >= (#sMax + 1) * 30 ; adapté
      Break
    EndIf
    i1 = i0
    Repeat
      K_30 = N2 / 30
      M_ = N2 % 30
      For I = 0 To 7 ; début de la partie qui va partir en fumée bientôt
        If M_ = M(I)
          sSet(K_30, I) ; adapté
          Break
        EndIf
      Next ; fin de la partie qui va partir en fumée bientôt
      N2 + N * gap(i1)
      i1 + 1
      i1 & 7
    Until N2 >= (#sMax + 1) * 30 ; adapté
  EndIf
  i0 + 1
  If i0 > 7
    i0 = 0
    K + 1
  EndIf
Until N > sqrMax
t1 = ElapsedMilliseconds()
Delay(1)


For I = 0 to #sMax
  For J = 0 To 7
    If s(I) >> J & 1 = 0 ; adapté
      P + 1
    EndIf
  Next
Next

; On affiche quantités et durée de notre algo dont on peut apparemment assortir de la palme du boulet d'or, tellement je n'ai méga rien optimisé... Technologiquement...
MessageRequester(Str((#sMax + 1) * 30) + " nb testés", Str(t1 - t0) + " ms" + Chr(10) + Str(P) + " nbs 1ers")