Bibm@th

Forum de mathématiques - Bibm@th.net

Bienvenue dans les forums du site BibM@th, des forums où on dit Bonjour (Bonsoir), Merci, S'il vous plaît...

Vous n'êtes pas identifié(e).

#476 21-11-2024 05:35:28

DrStone
Membre
Inscription : 07-01-2024
Messages : 273

Re : crible en python

Bonjour yoshi.

Je réagis rapidement sur la fin de ton précédent message

yoshi a écrit :

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.

Dernière modification par DrStone (21-11-2024 07:09:52)

Hors ligne

#477 21-11-2024 09:37:40

LEG
Membre
Inscription : 19-09-2012
Messages : 740

Re : crible en python

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
 

Dernière modification par LEG (29-11-2024 10:40:10)

Hors ligne

#478 21-11-2024 10:40:25

LEG
Membre
Inscription : 19-09-2012
Messages : 740

Re : crible en python

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")

 

Dernière modification par LEG (29-11-2024 10:38:56)

Hors ligne

#479 21-11-2024 14:38:18

yoshi
Modo Ferox
Inscription : 20-11-2005
Messages : 17 223

Re : crible en python

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

@+


Arx Tarpeia Capitoli proxima...

Hors ligne

#480 21-11-2024 15:00:42

LEG
Membre
Inscription : 19-09-2012
Messages : 740

Re : crible en python

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
@+

Dernière modification par LEG (24-11-2024 15:30:26)

Hors ligne

#481 25-11-2024 22:08:42

DrStone
Membre
Inscription : 07-01-2024
Messages : 273

Re : crible en python

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.

Hors ligne

#482 26-11-2024 10:00:16

LEG
Membre
Inscription : 19-09-2012
Messages : 740

Re : crible en python

Bonjour :
@DrStone

1)

void fill_crible(vector<unsigned> &crible, unsigned p)

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

 size_t lencrible = sqrt(limite)/30;

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

Dernière modification par LEG (26-11-2024 12:26:06)

Hors ligne

#483 26-11-2024 17:21:33

yoshi
Modo Ferox
Inscription : 20-11-2005
Messages : 17 223

Re : crible en python

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...)

@+


Arx Tarpeia Capitoli proxima...

Hors ligne

#484 26-11-2024 19:23:58

LEG
Membre
Inscription : 19-09-2012
Messages : 740

Re : crible en python

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

@+

Dernière modification par LEG (28-11-2024 12:23:19)

Hors ligne

#485 09-12-2024 08:20:57

LEG
Membre
Inscription : 19-09-2012
Messages : 740

Re : crible en python

Bonjour
@DrStone

Si cela peut faciliter le programme , je viens de voir qu'il n'est pas utile d'utiliser [ les Slices]

 ulonglong nslices = lencrible / 45000000, currentslice = 0;

car en effet:
Étant donné que j'utilise comme limite $n$ :

 size_t lencrible = sqrt(limite)/30;

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$

@+

Dernière modification par LEG (10-12-2024 09:25:10)

Hors ligne

#486 09-12-2024 21:53:20

DrStone
Membre
Inscription : 07-01-2024
Messages : 273

Re : crible en python

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).

Hors ligne

#487 10-12-2024 09:41:55

LEG
Membre
Inscription : 19-09-2012
Messages : 740

Re : crible en python

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...!

@+

Dernière modification par LEG (10-12-2024 09:44:47)

Hors ligne

Réponse rapide

Veuillez composer votre message et l'envoyer
Nom (obligatoire)

E-mail (obligatoire)

Message (obligatoire)

Programme anti-spam : Afin de lutter contre le spam, nous vous demandons de bien vouloir répondre à la question suivante. Après inscription sur le site, vous n'aurez plus à répondre à ces questions.

Quel est le résultat de l'opération suivante (donner le résultat en chiffres)?
cinquante huit plus soixante six
Système anti-bot

Faites glisser le curseur de gauche à droite pour activer le bouton de confirmation.

Attention : Vous devez activer Javascript dans votre navigateur pour utiliser le système anti-bot.

Pied de page des forums