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
- 10-12-2024 09: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 21: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 08: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 19: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
>>>
Tout à fait d'accord avec ta citation favorite ... en plus c'est valable de partout...
@+
- yoshi
- 26-11-2024 17: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 10: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 22: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 15: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⁶⁴...
========= 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
>>>
Je te dois le restau....! ou du chocolat ...
Dans l'attente : Merci mon ami
@+
- yoshi
- 21-11-2024 14:38:18
Re,
Donc ça fonctionne,
Je n'avais que peu de doutes à ce sujet au vu des conclusions que j'avais tirées dans l'EDIT de mon post #473 p.19...
Il y a bien quelqu'un qui savait que le candidate_range laissait passer des non premiers qu'il était nécessaire de purger ce qui était fait avec l'énorme liste sieve_list dans la def eratostene entièrement dévolue à ce boulot...
Il y avait encore l'infime possibilité que j'aie raté un autre appel à cette def même si
- j'avais fait la recherche directement avec Python
- j'avais copié/collé le prog complet dans mon traitement de textes et procédé à la même recherche...
C'est quand même invraisemblable cette histoire...
Pour un nb premier donné, les scories étaient des produits de deux nombres premiers (inférieurs, égaux ou supérieurs) :
[5, 7, 11, 13, 17, 19, 23, 25, 29, 31, 35, 37, 41, 43, 47, 49, 53, 55, 59, 61, 65, 67, 71, 73, 77, 79, 83, 85, 89, 91, 95, 97, 101, 103, 107, 109, 113, 115, 119, 121, 125, 127, 131, 133, 137, 139, 143, 145, 149, 151, 155, 157, 161, 163, 167, 169, 173, 175, 179, 181, 185, 187, 191, 193, 197, 199, 203, 205, 209, 211, 215, 217, 221, 223, 227, 229, 233, 235, 239, 241, 245, 247, 251, 253, 257, 259, 263, 265, 269, 271, 275, 277, 281, 283, 287, 289, 293, 295, 299, 301, 305, 307, 311, 313]
En partant de 5
on avait notamment
25 (5*5), 35 (5*7), 55 (5*11), 65 (5 *13),85 (5*17)....
En partant de 7 :
(35 déjà vu), 49 (7*7), 77 (7 *11), 91 (7*13), 119 (7*17), 133 (7 * 19)...
En partant de 11
( 55, 77 déjà vus)
121 (11 *11), 143 (11*13), 187 (11*17), 209 (11*19)...
En partant de 13 :
(65, 91, 143 déjà vus)
169 (13* 13), 221 (13*17),247 (13*19)
De 7 à 313 :
sans les scories
63 nombre premiers
avec les scories 104
soit +21 !!
31/63 = 1/3
La def eratostene avait donc à virer ici +33 % de faux premiers rien que pour n = 50000...
C'est tellement étonnant que m'interromps pour aller chercher la première apparition de la version avec yield
- ça me chiffonne de la voir si courte
- si elle commettait autant d'erreurs, pourquoi on ne s'en pas aperçu ?
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....
Donc, celui qui a créé candidate_range savait que en sortie cette def contenait des scories, qu'il fallait éliminer... Allez, à la titeuf : C pô bien ! C pô juste !... Moi, j'ai fait confiance et j'ai perdu du temps
Bon maintenant que j'ai relu les 11 premières pages, je sais ! Et je peux retourner à numpy et d'abord à def candiats voit ce que je peux faire pour elle...
Après, j'irais voit plus loin...
@+
- LEG
- 21-11-2024 10:40:25
Je viens de lancer à tout hasard 10¹⁸ + 20 et voici le résultat ( parfait , donc il y avait bien un bug avec la version précédente où il m'était impossible de cribler cette valeur n...)
1)
===== RESTART: /home/gilbert/Programmes/Crible _ sqrt de n _ EG_2N_mod30.py ====
Donnez n: 1000000000000000020
Nombre premiers[3:] : 230.07
Nombre premiers criblés famille 7 : 6356475 ----- 74.65
Nombres p' non congru 2n[P] < sqrt n , ou couple p'+q = 2n, de (1) à sqrt de 1000000000000000020 famille 7 : 646600 ----- 75.59
Pour info : avec le programme C++ il met 11 secondes pour cette même valeur inférieur à racine de n pour le même résultat ...
2)
Voila la limite $n = 9\times10^{18}$ supérieur à la limite actuelle , qui était de 4*10¹⁸
===== RESTART: /home/gilbert/Programmes/Crible _ sqrt de n _ EG_2N_mod30.py ====
Donnez n: 9000000000000000000
Nombre premiers[3:] : 3970.0
Nombre premiers criblés famille 7 : 18056145 ----- 226.37
Nombres p' non congru 2n[P] < sqrt n , ou couple p'+q = 2n, de (1) à sqrt de 9000000000000000000 famille 7 : 1433577 ----- 229.86
En C++ avec 4 familles :
https://www.cjoint.com/c/NKvlhURxcaA
---------------------------------
Donc : je met la nouvelle version complète, en ayant remplacé la première partie de python en référence et on verra avec numpy...
from time import time
from os import system
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:]
def E_Crible(premiers, n, fam):
start_crible = time()
n1 = int(n**0.5)
# On génère un tableau de N/30 cases rempli de 1 < racine carrée de n
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("crible Ératosthène :", crible) ## pour éditer le tableau Ératosthène criblé
print(f"Nombre premiers criblés 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
nbpremiers = len(premiers)
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")
- LEG
- 21-11-2024 09:37:40
Re @Yoshi:
c'est pratiquement la version python que j'avais au début qui était programmée de la sorte :
def eratostene(n):
n = int(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:])
return premiers[3:]
Qui est un peu plus lente que la version def eratosthène actuelle , pour une limite n=6*10¹⁷
Je vais donc faire ta modification et j'affiche le résultat , que l'on pourra comparer avec les deux résultats déjà affichés ...
===== RESTART: /home/gilbert/Programmes/Crible _ sqrt de n _ EG_2N_mod30.py ====
Donnez n: 60000
crible Ératosthène : [1, 1, 1, 1, 1, 1, 0, 0]
Nombre premiers criblés famille 7 : 6 ----- 0.0
crible É ET G: [1, 1, 0, 0, 0, 0, 0, 0]
Nombres p' non congru 2n[P] < sqrt n , ou couple p'+q = 2n, de (1) à sqrt de 60000 famille 7 : 2 ----- 0.0
1) Ça fonctionne parfaitement , [1=7] et [1=37] , comme tu peux le vérifier , 7 et 37 représente bien avec leur complémentaire par rapport à 2n = 120 000
deux couples de premiers qui vérifient la conjecture...
je vais indiquer le temps pour cette fonction (def eratosthène(n) afin de vérifier la perte ou le gain de temps...
2ème) teste n= 120 000 000 000 000
====================== RESTART: /home/gilbert/Programmes/Crible _ sqrt de n _ EG_2N_mod30.py =====================
Donnez n: 120000000000000
Nombre premiers[3:] : 2.1
Nombre premiers criblés famille 7 : 90531 ----- 0.68
Nombres p' non congru 2n[P] < sqrt n , ou couple p'+q = 2n, de (1) à sqrt de 120000000000000 famille 7 : 9459 ----- 0.71
>>>
temps mis par la def eratosthene : 2,1 secondes
3ème) teste : "" il est plus rapide "" Tu peux le vérifier au post ## 470 page précédente 19 on gagne 20 secondes par rapport à la version actuelle ... et 40 secondes avec l'autre version , que l'on peut abandonner...
===== RESTART: /home/gilbert/Programmes/Crible _ sqrt de n _ EG_2N_mod30.py ====
Donnez n: 600000000000000000
Nombre premiers[3:] : 112.8
Nombre premiers criblés famille 7 : 4988801 ----- 55.44
Nombres p' non congru 2n[P] < sqrt n , ou couple p'+q = 2n, de (1) à sqrt de 600000000000000000 famille 7 : 422407 ----- 56.33
- DrStone
- 21-11-2024 05:35:28
Bonjour yoshi.
Je réagis rapidement sur la fin de ton précédent message
Questions :
1. Le plus important : ça fonctionne ?
2. Vitesse : beaucoup de perte ?
3. limite maxi de n : changement ?
Je pars du principe que ça va fonctionner...
Toutes ces questions pourraient aisément trouver leurs réponses (enfin "aisément" selon ton envie, bien entendu, ainsi que ta capacité d’apprentissage — encore que ce n’est pas bien compliqué —) à chaque fois que tu te les poses (et donc globalement à chaque changement) à l’aide de ce qu’on appelle des tests unitaires (unit test).
Le but est de créer des tests, les plus simples possibles, sur une fonction qui s’exécutent à chacune de tes demandes pour vérifier que tout fonctionne correctement, à chaque fois.
Par exemple si tu écris ta propre fonction $prime$ qui teste si un nombre est premier, tu peux créer des tests unitaires pour tester si $2$ est premier (renvoie true), si $3$ est premier, si $4$ n’est pas premier (renvoie false), tester des cas plus généraux tels que s’assurer que tout nombre pair différent de $2$ n’est pas premier et enfin tester les cas un peu bizarres (s’assurer, par exemple, que tout nombre inférieur ou égal à 1 renvoie false — utile en python, notamment, ou un nombre peut prendre toute valeur, un peu moins en C ou on peut être que sur des entiers positifs —).
Si tes tests sont bien construits tu peux alors, aidé de ceux-ci, t’assurer que ta fonction $prime$ ne renvoie pas de nombres qui ne sont pas premiers ou de faux positifs (bien que ça n’ait pas toujours du sens pour une fonction $prime$ cette notion de « faux positif »).
Bien entendu avec ces tests il est possible de faire beaucoup plus encore mais dans un premier temps il me semble que c’est ce dont tu pourrais avoir le plus besoin.
Une bonne pratique est d’écrire tes tests avant ta fonction. Ça permet de saisir l’essence même de celle-ci et de la cloisonner. Tu peux alors décomposer ton problème en sous-problèmes plus simples à résoudre au fur et à mesure avec ta fonction afin de lui faire passer les tests un à un : aucune raison de lui faire réussir tous les tests en un seul jet.
Ça peut paraître long et sans intérêt de prime abord, mais si tu t’y intéresses vraiment (ne serait-ce qu’un peu), tu te rendras vite compte que ça t’évite beaucoup de perte de temps à écrire des print partout pour debugger ton programme : on ne peut, très rapidement, plus s’en passer.
- yoshi
- 20-11-2024 20:37:25
Re,
J'ai testé candidate_range vs la dernière version que j'avais retouchée...
Y a pas photo avec un n brut de 50000, le premier me fournit au moins une vingtaine (à la louche) de faux premiers (multiples) :
[5, 7, 11, 13, 17, 19, 23, 25, 29, 31, 35, 37, 41, 43, 47, 49, 53, 55, 59, 61, 65, 67, 71, 73, 77, 79, 83, 85, 89, 91, 95, 97, 101, 103, 107, 109, 113, 115, 119, 121, 125, 127, 131, 133, 137, 139, 143, 145, 149, 151, 155, 157, 161, 163, 167, 169, 173, 175, 179, 181, 185, 187, 191, 193, 197, 199, 203, 205, 209, 211, 215, 217, 221, 223, 227, 229, 233, 235, 239, 241, 245, 247, 251, 253, 257, 259, 263, 265, 269, 271, 275, 277, 281, 283, 287, 289, 293, 295, 299, 301, 305, 307, 311, 313]
et l'ancien:
[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]
Pourquoi ? je ne sais pas. Je verrais ça plus tard
Le seul intérêt de sieve_list est était de corriger cette aberration.
J'ai donc prévu de t'aider à t'en passer et de tout ce qu'il y avait autour...
Ça va être à toi de jouer (mdifications minimalisées) :
1. Tu commences par charger ton programme.
2. Tu supprimes les def candidate_range(n) et eratostene(n)
3. Tu enregistres ton programme sous un autre nom !!) impératif, hein...
4 Tu rajoutes la remplaçante:
def candidats(n):
n = int((2*n)**0.5)
m = (n-1) // 2
b = [True]*m
i = 0
p = 3
premiers = [2]
while p*p < n:
if b[i]:
premiers.append(p)
j = 2*i*i + 6*i + 3
while j < m:
b[j] = False
j = j + 2*i + 3
i += 1
p += 2
while i < m:
if b[i]:
premiers.append(p)
i += 1
p += 2
return premiers[3:] # 3 ou 2 . Si 3 --> 2, 3, 5 pas présents
5. Enfin, tu vas dans def main(n)
- tu mets un # devant premiers = eratostene(n)
- et dessous tu écris
premiers = candidats(n)
Questions :
1. Le plus important : ça fonctionne ?
2. Vitesse : beaucoup de perte ?
3. limite maxi de n : changement ?
Je pars du principe que ça va fonctionner...
Je vais redémarrer sur numpy et voir d'abord à modifier candidats, puis le reste...
@+
- LEG
- 20-11-2024 16:20:15
Re
Quel intérêt a-t-on de savoir où sont les premiers entre 1 et n ?
Absolument aucun ...du moment que l'on a la liste des nombres premiers $P\leqslant\sqrt{2n}$ .
Sauf ..., si cette fonction permet justement d'éliminer les multiples de $P$
- yoshi
- 20-11-2024 15:39:23
Re,
Encore une scorie je voulais vérifier les False apparaissant dans sieve_list...
Bin je m'en vais doinc me concentrer sur l'intérêt de sieve_list :
1. Avec sieve_list, on dispose de la position de tous les nombres non premiers parmi les entiers de 1 à n, et par ricochet les autres sont premiers . Quel intérêt a-t-on de savoir où sont les premiers entre 1 et n ?
2. On dispose pourtant, aussi de la liste des nombres premiers...
Si vraiment, je n'arrive pas à trouver la réponse, alors je me concentrerais sur le contraire de ce qui est fait : construire sieve_list à partir
de prime_E[2:] : je suis presque convaincu qu'il y a du temps à gagner : je devrais à pouvoir remplacer ces 3 boucles imbriquées (plus la
toute première) par des instructions numpy globales...
@+
[EDIT]
1ers constats
Q. Que fait la def eratostene(n) ?
R. Elle construit sieve_list et Prime_E...
Q. D'où est-elle appelée sachant que d'origine elle ne retourne que la liste de nombres premiers ?
R. Depuis la def main() qui récupère la liste des premiers générés...
Q. A quoi sert alors la sieve_list ?
Si candidate_range était fiable : à rien !!!
En fait son seul boulot c'est d'expurger, prime_E des "quelques" non-premiers générés par candidate_range...
Il faut savoir qu'en Python tout ce qui se passe dans une fonction est de l'ordre du local : tout calcul, tout résultat, tous les noms de variables s'ils ne sont pas retournés en fin de def avec Return restent totalement inconnus à l'extérieur de ladite def...