Forum de mathématiques - Bibm@th.net
Vous n'êtes pas identifié(e).
- Contributions : Récentes | Sans réponse
- Accueil
- » Programmation
- » crible en python
- » Répondre
Répondre
Résumé de la discussion (messages les plus récents en premier)
- LEG
- 20-06-2025 12:37:07
re bon le plu dur est passé alors ... c'est bien . Oui pour le module Numpy pour python , je crois que l'IA de ChatGPT , l'a utilisé pour me refaire un des programmes python de Goldbach ... mais en définitive , elle m'a dit qu'ils était très performant et le dernier que j'ai donc posté au post 490 , il ne va pas plus vite ...
Par contre en C++ , cela m'a permis de gagner de la mémoire , un peu de rapidité par rapport au c++ d'origine que je lui ai fourni et qu'on utilise depuis plusieurs année maintenant...
Poses lui la question si tu reprends avec Numpy , mais concrètement , cela n'avance guère; elle a fait une version , qui après le teste était moins rapide que la version que l'on utilise ,. Tu verras qu'elle est pas mal du tout , avec de très bonne idées , et une retranscription complète du programme immédiatement.. mais attention à chaque modification qu'elle fait, teste la modif ..., afin de lui transmettre les erreurs éventuelles ...
je me suis bien amusé ... et c'est assez bien fait par les concepteurs de ChatGPT
voici les résultats pour les deux limites n criblées relatif aux deux entiers pairs 2n ; et en utilisant que les nombres premiers $p'\leq\sqrt{}$ ($\sqrt{n}$) limitant le nombre de p' à cribler , pour vérifier la conjecture par famille ... Les deux limites $n$ : 1): 3*10¹⁸ et 2): 1,25 *10¹⁹.
========= RESTART: /home/gilbert/Programmes/Python/Crible_EG2_mod30.py =========
Donnez n: 300000000000000000
7.903 secondes
39905622 nombres premiers >5 dans l'intervalle [1, sqrt600000000000000000
Nombre premiers p' criblés de 1 à sqrt (sqrt n) famille 7 : 322 ----- 27.64
Nombres p' non congru 2n[P] < sqrt (sqrt n) , ou couple p'+q = 2n, de (1) à sqrt de 300000000000000000 famille 7 : 20 ----- 27.37
========= RESTART: /home/gilbert/Programmes/Python/Crible_EG2_mod30.py =========
Donnez n: 12500000000000000007
92.867 secondes
234954220 nombres premiers >5 dans l'intervalle [1, sqrt25000000000000000014
Nombre premiers p' criblés de 1 à sqrt (sqrt n) famille 7 : 759 ----- 190.57
Nombres p' non congru 2n[P] < sqrt (sqrt n), ou couple p'+q = 2n, de (1) à sqrt de 12500000000000000007 famille 7 : 64 ----- 186.94
--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
On peut utiliser n'importe qu'elle Famille , .. en fonction de la forme de n bien sûr , et j'ai remis le programme python de référence au #post 487 ci dessus .
https://www.dropbox.com/scl/fi/dubshyua … o7g7r&dl=0
https://www.dropbox.com/scl/fi/r7ec6xvp … lfwwg&dl=0
Voici les résultats pour étayer la reformulation de la conjecture de Godbach avec sa preuve raisonnement par l'absurde :
Les 6 familles i[30] qui décomposent cet entier 2n = 4*10¹⁹ +14 ("sachant que la décomposition réel pour ce 2n et les suivants, est de plusieurs milliards de couples (p'+q) = 2n ")
Dans un premier temps ci dessous , on va vérifier la (Différence du Nombre de p' criblés < sqrt n ; avec < sqrt (sqrt n) ; même limite et même Fam :)
========= RESTART: /home/gilbert/Programmes/Python/Crible_EG2_mod30.py =========
Donnez n: 20000000000000000007
3355.241 secondes
293944255 nombres premiers >5 dans l'intervalle [1, sqrt40000000000000000014
Nombre premiers p' criblés de 1 à (sqrt n) famille 7 : 26407786 ----- 327.65
Nombres p' non congru 2n[P] < (sqrt n) , ou couple p'+ q = 2n, de (1) à sqrt de 20000000000000000007 famille 7 : 2067239 ----- 314.9
========= RESTART: /home/gilbert/Programmes/Python/Crible_EG2_mod30.py =========
Donnez n: 20000000000000000007
3026.564 secondes
293944255 nombres premiers >5 dans l'intervalle [1, sqrt 40000000000000000014
Nombre premiers p' criblés de 1 à sqrt (sqrt n) famille 7 : 840 ----- 271.16
Nombres p' non congru 2n[P] < sqrt n , ou couple p'+q = 2n, de (1) à sqrt de 20000000000000000007 famille 7 : 53 ----- 247.8
========= RESTART: /home/gilbert/Programmes/Python/Crible_EG2_mod30.py =========
Donnez n: 20000000000000000007
3010.016 secondes
293944255 nombres premiers >5 dans l'intervalle [1, sqrt 40000000000000000014
Nombre premiers p' criblés de 1 à sqrt (sqrt n) famille 1 : 826 ----- 268.92
Nombres p' non congru 2n[P] < sqrt n , ou couple p'+q = 2n, de (1) à sqrt de 20000000000000000007 famille 1 : 72 ----- 240.79
========= RESTART: /home/gilbert/Programmes/Python/Crible_EG2_mod30.py =========
Donnez n: 20000000000000000007
3014.276 secondes
293944255 nombres premiers >5 dans l'intervalle [1, sqrt 40000000000000000014
Nombre premiers p' criblés de 1 à sqrt (sqrt n) famille 11 : 832 ----- 262.46
Nombres p' non congru 2n[P] < sqrt n , ou couple p'+q = 2n, de (1) à sqrt de 20000000000000000007 famille 11 : 75 ----- 248.59
========= RESTART: /home/gilbert/Programmes/Python/Crible_EG2_mod30.py =========
Donnez n: 20000000000000000007
3137.63 secondes
293944255 nombres premiers >5 dans l'intervalle [1, sqrt40000000000000000014
Nombre premiers p' criblés de 1 à sqrt (sqrt n) famille 13 : 834 ----- 270.91
Nombres p' non congru 2n[P] < sqrt(sqrt n) , ou couple p'+ q = 2n, de (1) à sqrt sqrt de 20000000000000000007 famille 13 : 50 ----- 242.56
========= RESTART: /home/gilbert/Programmes/Python/Crible_EG2_mod30.py =========
Donnez n: 20000000000000000007
3395.321 secondes
293944255 nombres premiers >5 dans l'intervalle [1, sqrt 40000000000000000014
Nombre premiers p' criblés de 1 à sqrt (sqrt n) famille 17 : 837 ----- 269.78
Nombres p' non congru 2n[P] < sqrt(sqrt n) , ou couple p'+ q = 2n, de (1) à sqrt sqrt de 20000000000000000007 famille 17 : 63 ----- 246.48
========= RESTART: /home/gilbert/Programmes/Python/Crible_EG2_mod30.py =========
Donnez n: 20000000000000000007
3010.208 secondes
293944255 nombres premiers >5 dans l'intervalle [1, sqrt 40000000000000000014
Nombre premiers p' criblés de 1 à sqrt (sqrt n) famille 23 : 841 ----- 261.88
Nombres p' non congru 2n[P] < sqrt(sqrt n) , ou couple p'+ q = 2n, de (1) à sqrt sqrt de 20000000000000000007 famille 23 : 56 ----- 239.74
***************************************************************************************
Les derniers testes > 2*10^{19} avec différentes Fam i[30]
========= RESTART: /home/gilbert/Programmes/Python/Crible_EG2_mod30.py =========
Donnez n: 22500000000000000007
5834.833 secondes
310921528 nombres premiers >5 dans l'intervalle [1, sqrt 45000000000000000014
Nombre premiers p' criblés de 1 à sqrt (sqrt n) famille 23 : 859 ----- 289.05
Nombres p' non congru 2n[P] < sqrt(sqrt n) , ou couple p'+ q = 2n, de (1) à sqrt sqrt de 22500000000000000007 famille 23 : 71 ----- 267.14
========= RESTART: /home/gilbert/Programmes/Python/Crible_EG2_mod30.py =========
Donnez n: 25000000000000000007
6269.74 secondes
326939392 nombres premiers >5 dans l'intervalle [1, sqrt 50000000000000000014
Nombre premiers p' criblés de 1 à sqrt (sqrt n) famille 23 : 877 ----- 323.48
Nombres p' non congru 2n[P] < sqrt(sqrt n) , ou couple p'+ q = 2n, de (1) à sqrt sqrt de 25000000000000000007 famille 23 : 67 ----- 317.6
Pour n = 3*10¹⁹ + 17
========= RESTART: /home/gilbert/Programmes/Python/Crible_EG2_mod30.py =========
Donnez n: 30000000000000000017
24281.945 secondes
356633994 nombres premiers >5 dans l'intervalle [1, sqrt 60000000000000000034
Nombre premiers p' criblés de 1 à sqrt (sqrt n) famille 17 : 918 ----- 379.8
Nombres p' non congru 2n[P] < sqrt(sqrt n) / 30 , ou couple p'+ q = 2n, de (1) à sqrt sqrt de 30000000000000000017 /30 famille 17 : 73 ----- 377.34
pour une estimation réelle dans cette Fam 17; de : 2 319 410 751 couples p'+q =2N
Très Cordialement Gilbert
- yoshi
- 20-06-2025 12:13:53
Bonjour LEG,
--> DropBox, ça fonctionne pour moi aussi, donc pas d'intervention supplémentaire de ma part nécessaire...
--> Numpy, j'étais bien parti mais je me suis vite aperçu que j'allais devoir réfléchir beaucoup plus,la doc, dans e domaine précis n'est pas satisfaisante. Je me suis retrouvé ensuite face à des problèmes personnels sur lesquels me pencher et enfin, cerise sur le gâteau, un matin ma machine, alors qu'elle s'était éteinte le soir normalement, le matin suivant, elle a refusé de lancer windows : elle ne le trouvait plus.
Là,comme un gros bêta, plus d'accès à mes fichiers, ni aux sites internet où je suis inscrit : je n'avais pas accès à mes mots de passe sur une source extérieure, ayant toujours négligé d'en faire...
Bref, après 5 jours d'essais, de tentatives diverses, je me suis résigné à admettre que faute d'outil logiciel adapté, je n'arriverai à rien.
Je me suis alors en chasse d'un magasin avec un technicien pour me dépanner... Certains me proposaient 3 semaines 1 mois de délai.
Finalement, j'en ai trouvé un qui m'a dit 10 jours... En fait, ça n'a duré qu'une semaine et coûté 35 €... Puis j'ai entrepris de déplacer mon antre dans une autre pièce...
Démontage, remontage du mobilier ; réagencement, ajout d'une extension que j'ai créée, montée et mise en place : j'ai bientôt fini d'ajouter d'autres petits espaces de stockage...
Je suis à 90% du rangement optimal et déjà à 120% de l'espace occupé avant...
Donc, je me repencherai (bientôt j'espère) sur le problème ; j'ai d'ailleurs découvert le module Simpy pour Python qui m'a l'air intéressant et dont j'ignorai l'existence...
@+
- LEG
- 19-06-2025 18:05:31
Re @Yoshi , donc si tu l'as téléchargé , est ce que tu peux créer le lien afin qu'il soit publié , avant que le lien que je viens de mettre ne soit plus actif , mais je vais voir si je peux aller sur ce site
voila ce que cela donne
https://www.dropbox.com/scl/fi/dubshyua … o7g7r&dl=0
Ok , c'est bon
Par contre c'est pas mal Chat GPT , pour faire modifier ou optimiser un crible . En ce qui me concerne pour lui poser aussi des questions, pour reformuler mon idée sur Goldbach
Ets ce que tu as essayé, de lui faire faire le crible de Goldbach , avec la version que tu voulais faire avec numpy ?
Sur les programmes en python que tu as écris , l'IA n' pas trouvé mieux pour les optimiser, mais je ne lui ai pas demandé avec numpy , car je ne sais pas comment lui expliquer .
les c++, par contre elle me les as repris , pour aller vers des limites n = 3X10²⁰ , j'ai essayé avec n = 3 x 10¹⁹ , ce qui est impossible dû à la limite en C++..??,
alors que pour la limite n = 3 x 10¹⁸ , c'est fait en 18 minutes ... ou un peu moins si on réduite le tableau De Ecrible à $\sqrt{}$($\sqrt{3*10^{18}}$).
Par contre en python on dépasse ces limites n...
Merci Yoshi , A + et passe une bonne soirée , leg
- yoshi
- 19-06-2025 14:31:18
Salut LEG,
Je pense avoir compris ce que tu voudrais que je fasse...
1. Rappel préliminaire : Bibmath ne dispose pas d'espace de stockage.
2. Ceci dit, Je suis allé voir si cjoint ne faisait plus de trucs bizarres... J'ai appris qu'ils changent meurs autorisations de stockage et que nous sommes priés de rapatrier très vite nos fichiers déposés chez eux : tous sont en cours de suppression progressive en partant des plus anciens...
3. Donc, je t'ai cherché autre chose.
J'ai pensé à
* DropBox
J'ai scrollé un peu et est constaté qu'ils avaient une option BASIC gratuite pas très généreuse (2 Go max).
A titre indicatif, j'ai téléchargé ton document, puisqu'il n'est pas consultable en ligne : ton pdf pèse 125 Ko.
Si j'ai bien compris, tu peux accorder les droits que tu veux...
* Google Drive. Voilà ce qu'en dit Wikipedia concernant
notamment les droits que Google s'arroge sur tes fichiers. Tu aurais droit à 15 Go (et non 2 comme Drop Box) gratuit...
@+
- LEG
- 19-06-2025 07:20:58
Re Bonjour :,
@Yoshi je viens de supprimer mon résumé posté hier après midi , que je remplace par le fichier suivant avec le lien de téléchargement ; ets ce que tu peux rendre ce pdf visible à durée indéterminé , ou copier le pdf pour l'inclure en latex sur ce post, sans que je sois obligé de télécharger un lien par semaine ; merci d'avance
- LEG
- 13-06-2025 10:33:52
Bonjour à tous,
Je vous remercie pour l’intérêt que vous portez à ce sujet.
Comme promis, je mets à disposition les deux versions modifiées des deux programmes Goldbach (Python et C++) du crible modulo 30 que j’ai construit en 2010 pour étudier la conjecture de Goldbach.
Puis en 2018 avec l'aide de notre bienfaiteur et modérateur Yoshi , qui m'a refait les programmes python , qui m'ont permis de les retranscrire en c++ ; dont je met la dernière version ci-dessous modifié et optimisé par chatGPT ce jour .
Ce crible permet d’analyser les entiers premiers dans une classe modulo 30 (1, 7, 11, 13, 17, 19, 23, 29), et de déterminer pour chaque valeur paire $2n$ si elle peut être exprimée comme une somme $p' + q$ où $p'$ et $q$ sont des nombres premiers dans une même famille modulo 30, , ou deux ; car $q$ le complémentaire de $p' \leqslant {n}$ par rapport à $2n$ , n'est pas obligatoirement de la même famille que $p'$ ; mais, où $p'$ n’est pas congru à $2n$ modulo 30, ce qui garantie , que son complémentaire $q$ est un nombre premier compris entre $n$ et $2n$
le choix de la famille , dépend de la valeur $n$ début un exemple ci dessous , qui est aussi expliqué dans le fichier joins par le lien suivant à durée limité jusqu'au 20.06.2025.
pour la valeur n = N de début :
N= 15k+1; Fam =(1,13,19); ⇒ 2n = 30k + 2 ⇒ 32 – 19 = 13 , ou 32 – 1 = 31 ⇒ la Fam complémentaire
N = 15k+2; Fam =(11,17,23); ⇒ 2n = 30k + 4 ⇒ 34 – 11 = 23 , ou 34 – 17 = 17
N = 15k+3; Fam =(7,29,13,23,17,19); 2n = 30k + 6
N = 15k+4; Fam =(1,7,19); 2n = 30k + 8
N = 15k+5; Fam =(1,7,13,19); 2n = 30k + 10
N = 15k+6; Fam =(1,11,13,19,23,29); 2n = 30k + 12
N = 15k+7; Fam =(1,7,13); 2n = 30k + 14
N = 15k+8; Fam =(17,23,29); 2n = 30k + 16
N = 15k+ 9; Fam =(1,7,11,17,19,29); 2n = 30k + 18
N = 15k+10; Fam =(11,29,17,23); 2n = 30k + 20
N = 15k+11; Fam =(11,23,29); 2n = 30k + 22
N = 15k+ 12; Fam =(1,7,11,13,17,23); 2n = 30k + 24
N = 15k+ 13; Fam =(7,13,19); 2n = 30k + 26
N = 15k+ 14; Fam =(11,17,29); 2n = 30k + 28
Je reste bien entendu à disposition si un mathématicien souhaite analyser ce fonctionnement ou l’approfondir. pour de grande valeur de début n > 3*10¹⁹
j'ai testé 2n > 3*10²² , que l'on peut incrémenté modulo 15 en saisissant :valeur début n et fin =valeur début +300 , l'algorithme effectuera le nombre de décomposition de $2n$successivement modulo 15 , ""ou par pas de 15"" , par famille choisit en conséquence .
Merci encore à la communauté BiBmath pour son aide précieuse.
voici le nouveau programme en c++
#include <vector>
#include <iostream>
#include <cmath>
#include <cstdlib>
#include <ctime>
using namespace std;
typedef unsigned long long ulonglong;
void fill_crible(vector<unsigned> &crible, unsigned p) {
crible.resize((p - 1) / 64 + 1);
size_t cs = crible.size();
unsigned lastnum = 64 * cs;
unsigned lastsieve = int(std::sqrt(double(lastnum)));
unsigned primesieved = 1;
crible[0] = 0xfffffffe;
for (size_t i = 1; i < cs; ++i)
crible[i] = 0xffffffff;
for (; primesieved <= lastsieve; primesieved += 2) {
size_t pos = primesieved / 2;
for (; pos < cs; ++pos) {
if (crible[pos / 32] & (1 << (pos % 32)))
break;
}
primesieved = 2 * pos + 1;
unsigned n = 3 * primesieved;
for (; n < lastnum; n += 2 * primesieved) {
pos = (n - 1) / 2;
crible[(pos / 32)] &= ~(1 << (pos % 32));
}
}
}
unsigned nextprime(vector<unsigned> &crible, unsigned p) {
++p;
if (p % 2 == 0)
++p;
size_t pos = (p - 1) / 2;
size_t cs = crible.size() * 32;
if (2 * cs + 1 <= p)
return -1;
for (; pos < cs; ++pos) {
if (crible[pos / 32] & (1 << (pos % 32)))
return 2 * pos + 1;
}
return -1;
}
size_t ECrible(const vector<ulonglong> &premiers, ulonglong n, int fam, vector<bool> &crible, size_t lencrible) {
clock_t cl = clock();
size_t nbpremiers = premiers.size();
vector<ulonglong> indices(nbpremiers);
for (size_t i = 0; i < nbpremiers; ++i) {
ulonglong p = premiers[i];
ulonglong produit;
int GM[] = {7, 11, 13, 17, 19, 23, 29, 31};
for (size_t j = 0; j < sizeof(GM) / sizeof(int); ++j) {
produit = p * GM[j];
if (produit % 30 == static_cast<ulonglong>(fam)) {
produit /= 30;
break;
}
}
indices[i] = produit;
}
ulonglong nslices = lencrible / 45000000;
if (nslices == 0) nslices = 1;
for (ulonglong currentslice = 0; currentslice < nslices; ++currentslice) {
size_t slicelimit = (currentslice + 1 == nslices) ? lencrible : (currentslice + 1) * (lencrible / nslices);
for (size_t i = 0; i < nbpremiers; ++i) {
ulonglong p = premiers[i];
size_t index;
for (index = indices[i]; index < slicelimit; index += p)
crible[index] = 0;
indices[i] = index;
}
}
size_t total = 0;
for (size_t index = 0; index < lencrible; ++index)
total += static_cast<int>(crible[index]);
cout << " Nbr p' criblés Fam " << fam << " < à sqrt " << n << " : " << total << " time " << (clock() - cl) * 1e-6 << endl;
return total;
}
size_t GCrible(const vector<ulonglong> &premiers, ulonglong n, int fam, vector<bool> &crible, size_t lencrible) {
clock_t cl = clock();
size_t nbpremiers = premiers.size();
ulonglong n2 = 2 * n;
vector<ulonglong> indices(nbpremiers);
for (size_t i = 0; i < nbpremiers; ++i) {
ulonglong p = premiers[i];
ulonglong reste = n2 % p;
if (reste % 2 == 0) reste += p;
ulonglong pi2 = 2 * p;
while (reste % 30 != static_cast<ulonglong>(fam))
reste += pi2;
reste /= 30;
indices[i] = reste;
}
ulonglong nslices = lencrible / 45000000;
if (nslices == 0) nslices = 1;
for (ulonglong currentslice = 0; currentslice < nslices; ++currentslice) {
size_t slicelimit = (currentslice + 1 == nslices) ? lencrible : (currentslice + 1) * (lencrible / nslices);
for (size_t i = 0; i < nbpremiers; ++i) {
ulonglong p = premiers[i];
size_t index;
for (index = indices[i]; index < slicelimit; index += p)
crible[index] = 0;
indices[i] = index;
}
}
size_t total = 0;
for (size_t index = 0; index < lencrible; ++index)
total += static_cast<int>(crible[index]);
cout << "Nombre couple criblés famille " << fam << " entre " << n << " et " << 2 * n << " : " << total << " time " << (clock() - cl) * 1e-6 << endl;
return total;
}
int main() {
vector<unsigned> temp;
ulonglong debut = 3000000000000000;
ulonglong fin = 3000000000000015;
vector<int> familles = {7, 11, 13, 17, 19, 23, 29, 31}; // attention, on sélection les familles en fonction de la valeur n début
for (size_t i = 0; i < familles.size(); ++i) {
int fam = familles[i];
for (ulonglong limite = debut; limite < fin; limite += 15) {
cout << "famille : " << fam << " limite : " << limite << endl;
double sqrt2N = sqrt(2.0 * static_cast<double>(limite));
fill_crible(temp, static_cast<unsigned>(sqrt2N));
vector<ulonglong> premiers;
for (ulonglong p = 7; p <= static_cast<unsigned>(sqrt2N); ) {
premiers.push_back(p);
p = nextprime(temp, static_cast<unsigned>(p));
if (p == static_cast<unsigned>(-1)) break;
}
size_t lencrible = static_cast<size_t>(sqrt(static_cast<double>(limite)) / 30.0);
vector<bool> crible(lencrible, true);
ECrible(premiers, limite, fam, crible, lencrible);
GCrible(premiers, limite, fam, crible, lencrible);
}
}
}
en c++ dans le programme on sélectionne toujours la famille modulo 30 compatible avec la valeur $n$ début , tel que 2n - fam i ne soit pas un multiple de 3 ou de 5.
exemple , pour n multiple de 30 les 8 famille sont compatibles mais si n = 30 001 , donc 2n = 60 002 seul 3 familles 1 sont compatibles, la famille i =1 ,13 ou 19.... etc ...cela est expliqué dans le pdf joint plus haut
------------------------
le nouveau programme en Python
from time import time
from time import perf_counter
from os import system
import math
def candidats(n):
#n = int(input("Entrez le nombre n "))
begin = perf_counter()
n1 = 2*n
length = int((n1)**0.5) // 3
if n%3 == 0 or n%3 == 1 and n%6 != 1: length -= 1
flags = [True] * length
number = 1
addition = 4
toggle = 6
for indexe in range(length):
number += addition
addition = toggle - addition
if not flags[indexe]: continue
start = (number * number *2 - 5) // 6
if start >= length: break
step = 2 * number
flags[start::step] = [False] * ((length - start + step - 1) // step)
advance = (indexe + 2) // 2
start += number - 2*advance + (indexe%2)*4*advance
flags[start::step] = [False] * ((length - start + step - 1) // step)
print(round(perf_counter()-begin, 3), "secondes")
print(f"{sum(flags)-1} nombres premiers >5 dans l'intervalle [1, sqrt {2*n}")
premiers = [2, 3] + [i//2*6+5+i%2*2 for i in range(length) if flags[i]]
#print(premiers[3:])
return premiers[3:]
def E_Crible(premiers, n, fam):
start_crible = time()
nbpremiers = len(premiers)
n1 = int(n**0.5) ## ou #n pour ne pas limiter à la racine carrée de n, le nombre de p' criblés
n2 = int(n1**0.5) ## pour générer un tableau de n/30 cases rempli de 1 ou, n1 = sqrt (sqrt n), puis n1/30
lencrible = n2//30 ## ou n//30 ; ou n1//30 pour augmenter le nombre de couples p'+q = 2n
crible = [1 for i in range(lencrible)] ## c'est plus propre comme ça
GM = [7,11,13,17,19,23,29,31]
## On calcule les produits :
for a in premiers:
for b in GM:
j = a * b
if j%30 == fam:
index = j // 30 ## Je calcule l'index et On crible directement à partir de l'index
for idx in range(index, lencrible, a): ## index qui est réutilisé ici...
crible[idx] = 0
total = sum(crible)
#print(nbpremiers)
#print("crible Ératosthène :", crible) ## pour éditer le tableau Ératosthène criblé
print(f"Nombre premiers p' criblés de 1 à sqrt (sqrt n) famille {fam} : {total} ----- {int((time()-start_crible)*100)/100}")
return crible,lencrible
def GCrible_2n(premiers, crible, lencrible, n, fam):
start_crible = time()
# On calcule les restes: r = 2*n/P
n2 = 2*n
for premier in premiers:
reste = n2 % premier
#print(reste)
if reste % 2 == 0:
reste += premier
p2 = 2*premier
## tant que reste % 30 != fam on fait reste += p2
while reste % 30 != fam:
reste += p2
## Ensuite on divise reste par 30 pour obtenir l'index
reste //= 30
## On crible directement à partir de l'index le tableau d'Ératosthène
for index in range(reste, lencrible, premier):
crible[index] = 0
total = sum(crible)
#print("crible É ET G:", crible) ## éditer le tableau criblé É et G
print(f"Nombres p' non congru 2n[P] < sqrt (sqrt n) , ou couple p'+q = 2n, de (1) à sqrt sqrt {n} famille {fam} : {total} ----- {int((time()-start_crible)*100)/100}")
def demander_n():
n = input("Donnez n: ")
n = int(n.strip().replace(" ", ""))
#n = int(30 * round(float(n)/30))
return n
def main():
## On demande n a l'utilisateur
n = demander_n()
## On récupère les premiers de 7 à √2n
premiers = candidats(n)
start_time = time()
## On crible
fam=7 ## ou 1, 7, 11, 13, 17, 19, 23, 29, au choix en fonction de n
crible,lencrible=E_Crible(premiers, n, fam)
GCrible_2n(premiers, crible, lencrible, n, fam)
main()
system("pause")
Proposition (Stabilité des solutions de Goldbach dans une famille modulo 30 lorsque la limite du crible progresse modulo 15 par Famille fixée, on définit $A\leq{n}$ , un entier naturel positif premiers p' ou pas, que l'on va cribler...d'abord par Ecrible qui élimine les $A\neq{p'}$ et ensuite par Gcrible , qui élimine les $p'\equiv{2nk}[p]$.)
Soit une famille fixée $Ff={p′∈N∣p′≡f\,mod30}$, où $f∈{1,7,11,13,17,19,23,29}$ est un résidu premier $modulo\; 30$.
On fixe un entier $n0$ assez grand et on considère les entiers pairs successifs de la forme
$2nk=2n0+30k$,avec $k∈N$.
On définit $Sf(nk)$ comme le nombre de décompositions de $2nk$ en une somme
$2nk=p′+q$,
avec $p′∈Ff $ et $q$ premier, sous réserve que $p′≤nk$ et que $p′$ et $q=2nk−p′ $ soient tous deux premiers, ce qui implique par conséquent $p'\not\equiv{2nk}[p]$
Alors, le crible appliqué à $Ff$ (d'abord par élimination des multiples de petits premiers $p≤2n0$ , puis par exclusion des $p′$ tels que $2nk≡p′modp)$ garantit la propriété suivante:
Si $Sf(n0)>0$, alors $Sf(nk)≥Sf(n0)$ pour tout $k≥1$.
Autrement dit, le nombre de solutions dans une famille modulo 30 ne peut pas décroître jusqu'à zéro , quand on fait croître $2n$ de $30$ en $30$ dans cette famille pour toute famille fixée et pour une limite $n\geq{150}$.
Cette propriété repose sur un fait crucial du crible : le décalage congruent $2nk↦2nk+1$ entraîne un simple décalage cyclique d'un rang des positions exclues $(modulo p)$, mais ne détruit pas d’informations afin de conserver l'égalité récurrente (2n – A) ⇔ (2n +30) – (A + 30) ,
équivalent à (A+30)$\not\equiv$(2N+30) [P] — les entiers non éliminés à l’étape précédente sont "réinjectés" aux mêmes intervalles.
? Conséquence heuristique forte :
Cette récurrence implicite induite par la structure du crible permet d’affirmer que pour toute famille valide $\;modulo\; 30$ et tout $n0$ fixé avec $Sf(n0)>0$, on a :
$v$ la conjecture de Goldbach.$∀k≥0,2nk=2n0+30k$ vérifie la conjecture de Goldbach.
Et donc, il devient impossible de rencontrer un entier pair $2n$ sans décomposition, dans la progression $2n0+30k$, pour une famille fixée.
Par conséquent, on peut affirmer : que $p'$ et $q$ premiers ne sont pas indépendant l'un de l'autre , car $q$ dépend de la congruence de $p'$ ainsi , la probabilité que :
$p'\not\equiv{2n}[P]$ ce qui implique $2n = p' + q$ vaut environ $\frac{1}{Ln\,n \,* \,Ln\,2n}$ ; d'où le nombre minimum de couples $(p' + q)$ par famille , vaut environ au minimum : ($\frac{n}{Ln\,n\,*\,Ln\,2n}$) / 8.
Car dans le cas contraire , cela implique qu'aucun entier $A\not\equiv{2nk}[p]$ ne précédait aucun $p'$ au rang $n-1; n-2; n-3 ...n-k$ lors des limites précédente $ n-1 ; n-2 ; n-3 ...n-k$ ce qui est contraire aux limites $n$ vérifiées précédemment , par l'algorithme de Goldbach.
Ce qui rend impossible la supposition que $2n + 2$ ou $2n + 30$ ne se décomposerait pas en une somme de deux nombres premiers.
Dernière version utilisant les _uint128_t pouvant tester des limites n = ou > 9*10¹⁸, en limitant les $p'<\sqrt{n}$ du crible Ératosthène , en peu de temps; avec le concourt aimable de l’équipe [chatGPT]
#include <iostream>
#include <vector>
#include <cmath>
#include <thread>
#include <cstdlib>
#include <mutex>
#include <ctime>
using namespace std;
typedef __uint128_t u128;
typedef unsigned long long u64;
mutex output_mutex;
void fill_crible(vector<unsigned> &crible, unsigned pmax) {
crible.resize((pmax - 1) / 64 + 1, 0xffffffff);
crible[0] &= ~1;
unsigned limit = sqrt(pmax);
for (unsigned i = 3; i <= limit; i += 2) {
if (crible[i / 64] & (1 << ((i / 2) % 32))) {
for (unsigned j = i * i; j < pmax; j += 2 * i) {
crible[j / 64] &= ~(1 << ((j / 2) % 32));
}
}
}
}
unsigned nextprime(const vector<unsigned> &crible, unsigned p) {
if (p <= 2) return 3;
for (unsigned i = p + 2; i < crible.size() * 64 * 2; i += 2) {
if (crible[i / 64] & (1 << ((i / 2) % 32))) return i;
}
return -1;
}
size_t ECrible(const vector<u64> &premiers, u128 n, int fam, vector<uint8_t> &crible) {
size_t len = crible.size();
vector<u64> indices(premiers.size());
int GM[] = {7, 11, 13, 17, 19, 23, 29, 31};
for (size_t i = 0; i < premiers.size(); ++i) {
u64 p = premiers[i];
for (int g : GM) {
u64 prod = p * g;
if (prod % 30 == static_cast<u64>(fam)) {
indices[i] = prod / 30;
break;
}
}
}
for (size_t i = 0; i < premiers.size(); ++i) {
u64 p = premiers[i];
for (size_t j = indices[i]; j < len; j += p) {
crible[j] = 0;
}
}
size_t total = 0;
for (uint8_t c : crible) total += c;
return total;
}
size_t GCrible(const vector<u64> &premiers, u128 n, int fam, vector<uint8_t> &crible) {
size_t len = crible.size();
u128 n2 = 2 * n;
vector<u64> indices(premiers.size());
for (size_t i = 0; i < premiers.size(); ++i) {
u64 p = premiers[i];
u64 r = static_cast<u64>(n2 % p);
if (r % 2 == 0) r += p;
u64 pi2 = 2 * p;
while (r % 30 != static_cast<u64>(fam)) r += pi2;
indices[i] = r / 30;
}
for (size_t i = 0; i < premiers.size(); ++i) {
u64 p = premiers[i];
for (size_t j = indices[i]; j < len; j += p) {
crible[j] = 0;
}
}
size_t total = 0;
for (uint8_t c : crible) total += c;
return total;
}
void traiter_famille(u128 n, int fam, const vector<u64> &premiers) {
clock_t start = clock();
cout << "Durée : " << (clock() - start) * 1e-6 << " s" << endl;
size_t lencrible = static_cast<size_t>(sqrt((long double)n)) / 30;
vector<uint8_t> crible(lencrible, 1);
ECrible(premiers, n, fam, crible);
size_t total = GCrible(premiers, n, fam, crible);
lock_guard<mutex> lock(output_mutex);
cout << "Famille " << fam << " pour n = ";
cout << (u64)(n / 1000000000000000000ULL) << "e18 : ";
cout << total << " p′ vérifiant conject (temps = " << (clock() - start) * 1e-6 << " s)" << endl;
}
int main() {
u128 debut = 1000000000000000020ULL;
u128 fin = debut + 45; // augmente la limite n par pas de 15
for (u128 n = debut; n < fin; n += 15) {
cout << "\n=== n = " << (u64)(n / 1000000000000000000ULL) << "e18 ===\n";
double sqrt2N = sqrt((long double)(2 * n));
vector<unsigned> temp;
fill_crible(temp, static_cast<unsigned>(sqrt2N));
vector<u64> premiers;
for (unsigned p = 7; p <= static_cast<unsigned>(sqrt2N); ) {
premiers.push_back(p);
p = nextprime(temp, p);
if (p == static_cast<unsigned>(-1)) break;
}
vector<thread> threads;
for (int fam : {7,1,13,19}) {
threads.emplace_back(traiter_famille, n, fam, cref(premiers));
}
for (auto &t : threads) t.join();
}
return 0;
}
https://www.dropbox.com/scl/fi/dubshyua … tcwep&dl=0
https://www.dropbox.com/scl/fi/r7ec6xvp … lfwwg&dl=0
Bien cordialement,
Gilbert
- LEG
- 19-03-2025 17:14:23
Bonjour
@Yoshi ; je viens de faire un test avec cet algorithme de Goldbach en prenant la limite n à cribler $10^19 + 16 en utilisant la famille 7 modulo 30
et et ça passe... alors qu'avec le programme en c++ , lorsque je saisie la même valeur j'ai un beug...
voici le résultat avec python pour $10^{19}$ et un peu plus...:
Comme tu le vois en définitive on pourrait tester cette conjecture au minimum jusqu'à une limite $n=10^{30}$ sans souci avec un calculateur et par famille... Ce qui n'a jamais été fait... En utilisant ce principe , c'est à dire, il est inutile d'utiliser tous les nombres premiers < à n pour cribler la congruence de ces nombres premiers..
Le plus long c'est dans la première partie du programme Ératosthène , pour l'extraction des nbr Primes $\leqslant\sqrt{n}$) que l'on va utiliser ensuite pour cribler .... que je viens de modifier voir ci-dessous
Par exemple ce programme est très rapide ("en l'adaptant a la première partie du programme Goldbach en référence actuel post #478") avec la même limite N ,
Je l'ai modifié pour cribler jusqu'à la racine carrée de 2n, afin d'utiliser les nombres premiers inférieur à racine de 2n.
il ne met que 60 seconde pour extraire les nombre premiers $\leqslant\sqrt{2n}$ au lieu de 3600 dans le programme actuel ...
======== RESTART: /home/gilbert/Programmes/Python/3. Gcrible . mod 2.py ========
Entrez le nombre maximum 4472135954 = racine de $2n$ , pour n = 10000000000000000016
66.302 secondes
211260428 nombres premiers dans l'intervalle [1, 4472135954
(" la première partie (def Ératosthène utilise 98% de la mémoire ram...) Donc impossible d'aller plus loin...")
https://www.dropbox.com/scl/fi/dubshyua … tcwep&dl=0
https://www.dropbox.com/scl/fi/r7ec6xvp … lfwwg&dl=0
Ça y est j'ai réussi a inclure ce petit programme à la place de la première partie actuelle , pour retourner les nombres primes ou premiers [3:] , comme le fait la première partie du programme actuel , ci-dessous , en lui incluant aussi from time import perf_counter: ..
.
J'ai modifié des lignes de programme dans cette fonction programmée, pour qu'il le prenne en compte dans le programme actuel au post #478 , ci-dessus :
Voila le nouveau programme de référence et le résultat pour la même limite n
from time import time
from time import perf_counter
from os import system
import math
def candidats(n):
#n = int(input("Entrez le nombre n "))
begin = perf_counter()
n1 = 2*n
length = int((n1)**0.5) // 3
if n%3 == 0 or n%3 == 1 and n%6 != 1: length -= 1
flags = [True] * length
number = 1
addition = 4
toggle = 6
for indexe in range(length):
number += addition
addition = toggle - addition
if not flags[indexe]: continue
start = (number * number *2 - 5) // 6
if start >= length: break
step = 2 * number
flags[start::step] = [False] * ((length - start + step - 1) // step)
advance = (indexe + 2) // 2
start += number - 2*advance + (indexe%2)*4*advance
flags[start::step] = [False] * ((length - start + step - 1) // step)
print(round(perf_counter()-begin, 3), "secondes")
print(f"{sum(flags)+2} nombres premiers dans l'intervalle [1, sqrt{2*n}")
premiers = [2, 3] + [i//2*6+5+i%2*2 for i in range(length) if flags[i]]
#print(premiers[3:])
return premiers[3:]
def E_Crible(premiers, n, fam):
start_crible = time()
nbpremiers = len(premiers)
n1 = int(n**0.5) ## ou # n1 = n pour ne pas limiter à la racine carrée de n
## pour générer un tableau de n/30 cases rempli de 1 ; ou n1 = racine carrée de n, puis n1/30
lencrible = n1//30
crible = [1 for i in range(lencrible)] ## c'est plus propre comme ça
GM = [7,11,13,17,19,23,29,31]
## On calcule les produits :
for a in premiers:
for b in GM:
j = a * b
if j%30 == fam:
index = j // 30 ## Je calcule l'index et On crible directement à partir de l'index
for idx in range(index, lencrible, a): ## index qui est réutilisé ici...
crible[idx] = 0
total = sum(crible)
#print(nbpremiers)
#print("crible Ératosthène :", crible) ## pour éditer le tableau Ératosthène criblé
print(f"Nombre premiers p' criblés de 1 à sqrt de n famille {fam} : {total} ----- {int((time()-start_crible)*100)/100}")
return crible,lencrible
def GCrible_2n(premiers, crible, lencrible, n, fam):
start_crible = time()
# On calcule les restes: r = 2*n/P
n2 = 2*n
for premier in premiers:
reste = n2 % premier
#print(reste)
if reste % 2 == 0:
reste += premier
p2 = 2*premier
## tant que reste % 30 != fam on fait reste += p2
while reste % 30 != fam:
reste += p2
## Ensuite on divise reste par 30 pour obtenir l'index
reste //= 30
## On crible directement à partir de l'index le tableau d'Ératosthène
for index in range(reste, lencrible, premier):
crible[index] = 0
total = sum(crible)
#print("crible É ET G:", crible) ## éditer le tableau criblé É et G
print(f"Nombres p' non congru 2n[P] < sqrt n , ou couple p'+q = 2n, de (1) à sqrt de {n} famille {fam} : {total} ----- {int((time()-start_crible)*100)/100}")
def demander_n():
n = input("Donnez n: ")
n = int(n.strip().replace(" ", ""))
#n = int(30 * round(float(n)/30))
return n
def main():
## On demande n a l'utilisateur
n = demander_n()
## On récupère les premiers de 7 à √2n
premiers = candidats(n)
start_time = time()
## On crible
fam=7 ## ou 1, 7, 11, 13, 17, 19, 23, 29, au choix en fonction de n
crible,lencrible=E_Crible(premiers, n, fam)
GCrible_2n(premiers, crible, lencrible, n, fam)
main()
system("pause")
----------------------------------------------------------------
pour n = 1,75*10¹⁹
========= RESTART: /home/gilbert/Programmes/Python/Crible_EG2_mod30.py =========
Donnez n: 17500000000000000017
1264.982 secondes
275816079 nombres premiers >5 dans l'intervalle [1, sqrt35000000000000000034
Nombre premiers p' criblés de 1 à sqrt de n famille 7 : 819 ----- 241.28
Nombres p' non congru 2n[P] < (sqrt (sqrt n))/30 , ou couple p'+q = 2n, de (1) à sqrt sqrt de 17500000000000000017 famille 7 : 71 ----- 227.42
fichier pdf modifié :
https://www.dropbox.com/scl/fi/dubshyua … tcwep&dl=0
- LEG
- 10-12-2024 08:41:55
Bonjour @DrStone
Ok , d'autant que pour un tableau de 600 000 000 nombres à cribler je ne pense , qu ça ne changerait grand chose... Je me suis amusé à modifier la valeur des slices , sans que cela change grand chose ...
C'était intéressant lorsque je criblai jusqu'à la limite n = 9 500 000 000 000 cela me permettait d'atteindre cette limite ... avec un peu de temps et beaucoup de mémoire utilisée...
En définitive seul le résultat compte, le fait de ne cribler qu'une partie des nombres premiers $p'$ inférieur à la limite $\sqrt{2^{64}}$ permet de se faire une très bonne idée sur la répartition par famille , du nombre de couples $p' + q = 2n$ afin de calculer ou de vérifier , des fonctions qui donnent un minimum de solutions...
Même en utilisant le programme Python tel quel , cité en référence ; mais avec un peu plus de temps ...
On peut d'ailleurs vérifier avec cette méthode par Famille , que si la conjecture avait été fausse , elle le serait à partir d'une petite limite $n$ et non lorsque $n$ tend vers l'infini...!
@+
- DrStone
- 09-12-2024 20:53:20
Bonsoir LEG.
Bonne question. Il faudrait que je prenne le temps de regarder ce que j’ai fait mais il me semble toutefois bien que j’ai transformé ce passage (ou ce qui se trouvait aux alentours).
- LEG
- 09-12-2024 07:20:57
Bonjour
@DrStone
Si cela peut faciliter le programme , je viens de voir qu'il n'est pas utile d'utiliser [ les Slices]
car en effet:
Étant donné que j'utilise comme limite $n$ :
On n'est donc pas obligé de slicer...non ?
Car la taille maximum du tableau à cribler ne ferait que $\sqrt\frac{9\times{10^{18}}}{30}$ = $547722557$
@+
- LEG
- 26-11-2024 18:23:58
Re Yoshi
, Je sais que tu ne m'oublies pas... C'est simplement une histoire de temps..
Donc moi ça me va , mais dommage que personne ne puisse t'aider concrètement avec Numpy... heureusement , tu es autant acharné que moi pour trouver la solution... Donc je ne me fais aucun souci , tu en viendras à bout.
Pour en revenir à cette instruction :
dans le tableau, si la condition est vérifiée alors tu remplaces True par False ... et on peut même ajouter : sinon tu remplaces par "autre chose" (ou laisse tel quel)...
Il me semblait que tu n'avais plus besoin d'utiliser True et False...
dans les deux autres parties de l'algorithme ECrible et GCrible ... car on utilise simplement le principe d'ÉRATOSTHÈNE EN PARTANT DE L'INDEX...
Donc je suppose que c'est toujours pour la première partie avec la fonction def candidats (n) que tu veux modifier...
Est ce que dans ce cas il ne faudrait pas revenir, à retourner deux liste de premiers , comme tu l'avais fait :
1) les premiers $P\leqslant\sqrt{n}$ pour la fonction def E_Crible(premiers, n, fam): si on gagne du temps dans cette fonction ,(ce qui n'est pas sûr...)
2) les premiers $P\leqslant\sqrt{2n}$ pour la fonction def GCrible_2n(premiers, crible, lencrible, n, fam):
Une fois modifiée cette première partie def candidats (n). Tu penses que cela va modifier considérablement le temps mis pour cette fonction ...?
Il est vrai que pour une grande valeur de n , cela prend pas mal de temps , pour cribler cette partie inférieur à racine carrée de n pour ECrible ou racine carrée de 2n pour la fonction GCrible .
Ce que tu avais déjà fait en retournant deux listes : les premiers inférieur à racine de n utiliser par ("ECrible) et les premiers inférieur à racine de 2n. utilisés par ("GCrible)..
Ce que je ne comprends "pas" : comment cette fonction def candidats (n) crible les nombres impairs < à racine de 2n (c'est un crible d'Ératosthène , classique)
Donc : j'ai fait un test en modifiant la partie (def candidats(n)) avec ce que tu avais fait en 2018 cette partie :
def candidats(n):
start_crible = time()
n = int((2*n)**0.5)
m = (n-1) // 2
limite=1+n
b = [True]*m
premiers = [2]
for i,p in enumerate(range(3,limite,2)):
if b[i]:
premiers.append(p)
j = 2*i*i + 6*i + 3
debut,pas=j,2*i+3
for j in range(debut,m,pas):
b[j] = False
debut=i
for i in range(debut,m):
if b[i]:
premiers.append(p)
p += 2
#print(premiers[3:])
print(f"Nombre premiers[3:] : {int((time()-start_crible)*100)/100}")
return premiers[3:]
Résultat on gagne 100 s (on passe de 230 S à 149 S pour la limite n=10¹⁸ +20
========= RESTART: /home/gilbert/Programmes/Python/Crible_EG2_mod30.py =========
Donnez n: 1000000000000000020
Nombre premiers[3:] : 149.12
Nombre premiers criblés famille 7 : 6356475 ----- 72.94
Nombres p' non congru 2n[P] < sqrt n , ou couple p'+q = 2n, de (1) à sqrt de 1000000000000000020 famille 7 : 646600 ----- 74.98
>>>
Mais avec cette modification de [def Candidats(n)] dans le programme il n'y a pas photo..
def candidats(n):
#n = int(input("Entrez le nombre n "))
begin = perf_counter()
n1 = 2*n
length = int((n1)**0.5) // 3
if n%3 == 0 or n%3 == 1 and n%6 != 1: length -= 1
flags = [True] * length
number = 1
addition = 4
toggle = 6
for indexe in range(length):
number += addition
addition = toggle - addition
if not flags[indexe]: continue
start = (number * number *2 - 5) // 6
if start >= length: break
step = 2 * number
flags[start::step] = [False] * ((length - start + step - 1) // step)
advance = (indexe + 2) // 2
start += number - 2*advance + (indexe%2)*4*advance
flags[start::step] = [False] * ((length - start + step - 1) // step)
print(round(perf_counter()-begin, 3), "secondes")
print(f"{sum(flags)+2} nombres premiers dans l'intervalle [1, sqrt{2*n}")
premiers = [2, 3] + [i//2*6+5+i%2*2 for i in range(length) if flags[i]]
#print(premiers[3:])
return premiers[3:]
résultat :
============= RESTART: /home/gilbert/Programmes/Crible_EG2_mod30.py ============
Donnez n: 1000000000000000020
17.332 secondes
70659843 nombres premiers dans l'intervalle [1, sqrt2000000000000000040
Nombre premiers p' criblés de 1 à sqrt de n famille 7 : 6356475 ----- 57.13
Nombres p' non congru 2n[P] < sqrt n , ou couple p'+q = 2n, de (1) à sqrt de 1000000000000000020 famille 7 : 646600 ----- 58.58
--------
Donnez n: 10000000000000000020
Nombres p' non congru 2n[P] < sqrt n , ou couple p'+q = 2n, de (1) à sqrt de 10000000000000000020 famille 7 : 1618201 ----- 190.78
on avait bien des nombres premiers parasites , mais surtout la def candidats(n) avait une grosse erreur comme tu l'as souligné.
Tout à fait d'accord avec ta citation favorite ... en plus c'est valable de partout...
https://www.dropbox.com/scl/fi/r7ec6xvp … lfwwg&dl=0
https://www.dropbox.com/scl/fi/dubshyua … tcwep&dl=0
@+
- yoshi
- 26-11-2024 16:21:33
Ave LEG,
Je ne t'oublie pas...
A force de fureter dans les tutos consacrés à numpy (en général, à mon goût, assez mal pensés...) j'ai fini par tomber sur une instruction qui m'a ouvert des horizsons...
Soit un tableau numpy, disons de 1 000 000 de cases remplis de nombres ou le cas simple (ça va te rappeler la fin de la def eratostene, remplis de True... Si tu veux y mettre des False, sous certaine condition, en Python pur, on est obligé de boucler sur les 1 000 000 de cases une par une et de les tester une par une...
Avec numpy, en gros, il suffit de lui dire :
dans le tableau, si la condition est vérifiée alors tu remplaces True par False ... et on peut même ajouter : sinon tu remplaces par "autre chose" (ou laisse tel quel)... Et ça prend une demi-ligne..
Je ne sais pas comment est pensée cette instruction, mais elle prend le tableau dans sa globalité (peu importe de connaître ou non sa longueur) et procède aux changements globalement...
Je suis tombé là-dessus hier soir. Si maintenant, je pouvais trouver quelque chose de convaincant pour remplacer 2 boucles imbriquées + des conditions par une instruction, j'aurais fait un grand pas en avant...
Mais les recherches via Google (qui d'autre ?) sont (très et trop) souvent frustrantes !
De plus,depuis quelques temps, une de mes filles, qui s'est engagée comme AESH prend son job très à cœur et me demande des fiches mesurant 7,5 cm X 10 cm (pour entrer dans une trousse) sur les conjugaisons (et ça, si elle veut en voir le bout - et je suis bien placé pour en parler - elle va devoir faire preuve de patience. En prime, maintenant, les mômes de primaire, sont en train de voir les h min s, les conversions et les opérations (+ et -).
Pour pouvoir aider les enfants, elle a besoin - elle - de maîtriser le sujet, j'estime, moi, devoir repartir de la source à savoir les bases de numération. Je sais, c'est ambitieux, ça n'a rien d'évident... C'est un mauvais moment à passer, mais lorsque c'est acquis, que de temps gagné ensuite
Quand je vois la formation mathématique que reçoivent les "Professeurs des écoles" (et ils n'y sont pour rien), ils auraient aussi du pain sur la planche : j'ai suivi ici, il y a déjà un certain temps, une jeune-femme qui se destinait à ce boulot et on avait passé en revue les différents points du programme et les exos qui allaient avec : l'épreuve de maths au concours ne lui avait pas causé de souci...
Donc, tu vois, je n'ai pas le temps de m'ennuyer, mais j'arrive encore à dégager 20 min à 1/2 h pour les recherches numpy, sans programmer, parce que programmer sans savoir ou je vais, j'ai déjà donné : c'est de la loterie...
Et je redégaine ma citation favorite : << Science sans conscience n'est que ruine de l'âme ! >> (Rabelais...)
@+
- LEG
- 26-11-2024 09:00:16
Bonjour :
@DrStone
1)
Cette fonction , à donc pour but , d'extraire tous les nombres premiers $P\leqslant\sqrt{2n}$ par rapport à la limite début n = fixée , que l'on va utiliser , pour ECrible et GCrible , "que l'on ne peut pas scinder" , il s'agit d'un petit crible d'Ératosthène.
2)
for (ulonglong limite = debut; limite < fin; limite += 15){
cout << "--> limite : " << limite << endl;
double sqrt2N = unsigned(std::sqrt(2 * double(limite)));
fill_crible(temp, sqrt2N); // [b]on rappelle les nombres premiers P < sqrt 2n , qui ont été extraits en début de programme[/b]
vector<ulonglong> premiers;
for (ulonglong p = 7; p <= sqrt2N;)
{
premiers.push_back(p);
p = nextprime(temp, p);
if (p == unsigned(-1))
break;
La totalité de cette fonction, a pour but d'utiliser les nombres premiers $P\leqslant\sqrt{2n}$ en indiquant le début et la fin de la limite n criblée ,
je suppose donc, que fill crible et de prendre tous ces nombres premiers P pour cribler la famille en question , du début à la fin de la limite n fixée , "avec le temps mis..."
Une fois la limite criblée finie : on augmente la valeur n = début , de 15 et on réitère avec ces même nombre premiers P , on crible la limite n+15 , suivante ...
Une fois que l'on a fini de cribler une "famille push_back" fixée, jusqu'à la limite (n modulo 15) fixée , ,
On réitère éventuellement avec une deuxième famille push_back ,fixée : idem du début à la fin de ""cette ou de ces limites n fixées""" avec:
toujours ces mêmes nombres premiers $P\leqslant\sqrt{2n}$ , qui ont été criblés , en début de programme par la fonction fill_crible :
Attention de ne pas confondre cette limite : début n = qui fixe la limite n des nombres premiers $P\leqslant\sqrt{2n}$ à extraire en début de programme ;
Avec la limite
qui elle, fixe la limite ou la taille du tableau à cribler par ces deux fonctions :
size_t ECrible et GCrible : et bien entendu, en utilisant tous les nombres premiers P de la fonction fill_crible...
soit on crible jusqu'à la limite n/30 , soit on crible uniquement , jusqu'à la racine carrée de n, puis divisée par 30.. pour les grandes valeurs de début n , fixé
En définitive, fill_crible : (c'est la même fonction utilisée par le programme python en question, référencé ci dessus , dans def eratosthene) que @yoshi vient de modifier ...en s'emm....à comprendre l'erreur qu'il y avait...
Programme python , que tu peux utiliser pour vérifier que les résultats sont identiques au C++.. en rentrant la même valeur n et la même famille : Fam i, et que la fonction Fill crible extrait bien les nombres premiers $P\leqslant\sqrt{2n}$ , dont on doit se servir pour les deux fonctions ECrible et GCrible ...
- DrStone
- 25-11-2024 21:08:42
Bonsoir.
J'ai travaillé ces derniers jours à refaire une bonne partie du code C++ et j'ai plutôt bien avancé.
Néanmoins je ne suis pas certain de bien comprendre ce que fait la fonction fill_crible et surtout de son champ d'action : que fait-elle, pourquoi elle le fait et, au besoin, pourquoi ne pas l'avoir scindée en plusieurs sous-fonctions ?
Si LEG veut bien m'éclairer du mieux possible sur celle-ci, je lui en serais reconnaissant.
- LEG
- 21-11-2024 14:00:42
Re :
La première apparition de "candidate_range" remonte au post #293, elle coïncide avec la même forme d'une def eratostene corrigeant les âneries de candidate_range....
Je viens de regarder la date , c'est bien lorsque j'étais au Québec, donc mon petit fils avait chargé ce programme, sur internet, pour extraire les premiers dans cette première partie , mais je sais qu'il n' a pas regarder en profondeur... il a simplement dû regarder la partie finale , qu'il y avait bien les nombre premiers P inférieur à racine de n, qui étaient extrait , sans plus... d'ailleurs mon commentaire (voici la dernière mouture...etc) en dit long...
à cette époque on ne s'intéressait uniquement à la partie GCrible : Goldbach et en rentrant du Québec j'ai posté cette partie En C++ faite Par Mr B Parisse ...
Donc ensuite on ne sait pas occupé de cette partie (def eratosthene[n])... du moment que le crible fonctionnait et qu'au final on avait bien les nombres premiers P pour la fonction suivante GCrible... et criblait bien les entiers A de 1 à n , qui étaient non congrus à 2n modulo P... Mais : Probablement aussi pour cela , que j'étais limité en python...
Tout comme hier , il était impossible de dépasser 10¹⁷ ... avec cette version et cette def eratosthene, que je viens de modifier dans les autres programmes python...
je viens de faire l'essais aujourd'hui avec la limite maximum possible : n = 1.75 * 10¹⁹ et ça passe soit , 2⁶⁴...
Avant :
========= RESTART: /home/gilbert/Programmes/Python/Crible_EG2_mod30.py =========
Donnez n: 17499999999999999990
Nombre premiers[3:] : 24846.0
Nombre premiers criblés famille 7 : 24780403 ----- 366.02
Nombres p' non congru 2n[P] < sqrt n , ou couple p'+q = 2n, de (1) à sqrt de 17499999999999999990 famille 7 : 1952935 ----- 318.06
>>>
Après changement de la def Candidat : pour la limite $n=(2.10^{19})+2$
Donnez n: 20000000000000000002
3688.793 secondes
293944258-4 nombres premiers dans l'intervalle [1, sqrt40000000000000000004]
Nombre premiers p' < sqrt n criblés, famille 30k+7 : 26407786 ----- 326.3
Nombres p' non congru 2n[P] < sqrt n , ou couple p'+ q = 2n, de (1) à sqrt de 20000000000000000002 famille 7 : 2287931 ----- 309.04
Je te dois le restau....! ou du chocolat ...
https://www.dropbox.com/scl/fi/r7ec6xvp … lfwwg&dl=0
Dans l'attente : Merci mon ami
@+