A propos de nombres premiers
Re: A propos de nombres premiers
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...
"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...
Re: A propos de nombres premiers
Quand il faut y aller, faut y aller !
Microsoft Windows 10 Famille 64 bits : Carte mère : ASRock 970 Extreme3 R2.0 : Carte Graphique NVIDIA GeForce RTX 3080 : Processeur AMD FX 6300 6 cœurs 12 threads 3,50 GHz PB 5.73 PB 6.00 LTS (x64)
Un homme doit être poli, mais il doit aussi être libre !
Un homme doit être poli, mais il doit aussi être libre !
Re: A propos de nombres premiers
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)
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.
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.
Mon avatar reproduit l'image de 4x1.8m présentée au 'Salon international du meuble de Paris' en janvier 2004, dans l'exposition 'Shades' réunisant 22 créateurs autour de Matt Sindall. L'original est un stratifié en 150 dpi.
Re: A propos de nombres premiers
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.
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.
Re: A propos de nombres premiers
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)
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.
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
A+
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
soit 1146 secondes9223372036854765809 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
A+
Dernière modification par PAPIPP le jeu. 03/nov./2016 19:55, modifié 3 fois.
Il est fort peu probable que les mêmes causes ne produisent pas les mêmes effets.(Einstein)
Et en logique positive cela donne.
Il est très fortement probable que les mêmes causes produisent les mêmes effets.
Et en logique positive cela donne.
Il est très fortement probable que les mêmes causes produisent les mêmes effets.
Re: A propos de nombres premiers
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...
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
Re: A propos de nombres premiers
@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 :
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.
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
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.
Mon avatar reproduit l'image de 4x1.8m présentée au 'Salon international du meuble de Paris' en janvier 2004, dans l'exposition 'Shades' réunisant 22 créateurs autour de Matt Sindall. L'original est un stratifié en 150 dpi.
Re: A propos de nombres premiers
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+
Une erreur a été corrigée dans le programme de recherche des nombres premiers.
http://www.purebasic.fr/french/viewtopi ... &start=120
A+
Il est fort peu probable que les mêmes causes ne produisent pas les mêmes effets.(Einstein)
Et en logique positive cela donne.
Il est très fortement probable que les mêmes causes produisent les mêmes effets.
Et en logique positive cela donne.
Il est très fortement probable que les mêmes causes produisent les mêmes effets.
Re: A propos de nombres premiers
Super PAPIPP. Merci pour la mise à jour.
Mon avatar reproduit l'image de 4x1.8m présentée au 'Salon international du meuble de Paris' en janvier 2004, dans l'exposition 'Shades' réunisant 22 créateurs autour de Matt Sindall. L'original est un stratifié en 150 dpi.
Re: A propos de nombres premiers
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à).
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à).
Mon avatar reproduit l'image de 4x1.8m présentée au 'Salon international du meuble de Paris' en janvier 2004, dans l'exposition 'Shades' réunisant 22 créateurs autour de Matt Sindall. L'original est un stratifié en 150 dpi.
Re: A propos de nombres premiers
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.
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+
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
….
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+
Dernière modification par PAPIPP le sam. 05/nov./2016 14:28, modifié 1 fois.
Il est fort peu probable que les mêmes causes ne produisent pas les mêmes effets.(Einstein)
Et en logique positive cela donne.
Il est très fortement probable que les mêmes causes produisent les mêmes effets.
Et en logique positive cela donne.
Il est très fortement probable que les mêmes causes produisent les mêmes effets.
Re: A propos de nombres premiers
@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.
?
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.
?
Re: A propos de nombres premiers
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.
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.
Il est fort peu probable que les mêmes causes ne produisent pas les mêmes effets.(Einstein)
Et en logique positive cela donne.
Il est très fortement probable que les mêmes causes produisent les mêmes effets.
Et en logique positive cela donne.
Il est très fortement probable que les mêmes causes produisent les mêmes effets.
Re: A propos de nombres premiers
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.
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.
Mon avatar reproduit l'image de 4x1.8m présentée au 'Salon international du meuble de Paris' en janvier 2004, dans l'exposition 'Shades' réunisant 22 créateurs autour de Matt Sindall. L'original est un stratifié en 150 dpi.
Re: A propos de nombres premiers
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.
A+
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
Il est fort peu probable que les mêmes causes ne produisent pas les mêmes effets.(Einstein)
Et en logique positive cela donne.
Il est très fortement probable que les mêmes causes produisent les mêmes effets.
Et en logique positive cela donne.
Il est très fortement probable que les mêmes causes produisent les mêmes effets.