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

#1 26-09-2020 02:37:21

Omhaf
Membre
Inscription : 16-01-2020
Messages : 38

Génération des nombres premiers : algorithme

Bonjour,

Quelqu'un a t il déjà réussi à formuler un algorithme pour générer les nombres premiers ?
Je viens d'en confectionner un basé sur la division par 12 de leurs carrés mais le seul hic est qu'il m'ajoute des nombres qui sont tous des produits de 2 nombres premiers
En effet sur les nombres premiers inférieurs à 1000 et qui sont de 168 nombres premiers  j'obtiens 33 de plus tous des produits de 2 nombres premiers.
Exemple :
211 et 223 sont des nombres premiers consécutifs mais entre eux j'obtiens également 221
221 = 13 x 17

Si le thème vous intéresse je peux fournir les détails
Merci

Hors ligne

#2 26-09-2020 08:31:30

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

Re : Génération des nombres premiers : algorithme

Bonjour
Ben sur le forum de programmation ce n'est pas les algorithmes (cribles) générant des nombres premiers qui manquent , le crible d'Ératosthène ou une de ses variante...

Si pour une limite n =1000 , ton algorithme te donne 33 nombres premiers c'est qu'il a un sérieux problème...Et en combien de temps ?

Qu'est ce que cela donne pour n = 600 000 000 000 ? En combien de temps ?
par exemple pour le mien , il me donne 2 875 943 853 nombres premiers de la forme 30k + 7 en 59 secondes

Commence par expliquer ton algorithme ...Si tu veux une réponse §

Hors ligne

#3 26-09-2020 08:59:45

Omhaf
Membre
Inscription : 16-01-2020
Messages : 38

Re : Génération des nombres premiers : algorithme

Bonjour LEG
Je crois que tu m'as mal compris,
relis mon poste stp
en plus des 168 nombres premiers inférieurs à 1000 j'ai 33 nombres en plus et ce qui les caractérisent tous est qu'ils sont des produits de 2 nombres premiers

Hors ligne

#4 26-09-2020 09:03:20

yoshi
Modo Ferox
Inscription : 20-11-2005
Messages : 15 084

Re : Génération des nombres premiers : algorithme

Re,

@Omhaf. Et les réponses concernant ta somme de carrés ne t'intéressent plus ?
Sauf erreur, tu fais probablement des calculs via une calculatrice, pas avec un langage de programmation, donc ton horizon est vraiment trop limité... Mais montre-nous ce que tu as imaginé..
Sache cependant que personne, même parmi les plus grands mathématiciens actuels n'a été capable de construire à coup sûr un nombre premier, ni de montrer que la conjecture de Syracuse était vraie...

@LEG
Quant à toi, d'ici quelques jours, je vais reprendre ton programme et le repenser en fonction de l'extension mathématique numpy de Python.
J'avais bricolé avec , l'an dernier et il n'y avait pas de changement. Mais c'était du bricolage, je vais essayer aussi le threading : parallélisation des calculs pour utiliser plusieurs des cœurs du processeur de nos bécanes : tout ce qu'on a pu écrire n'en utilise qu'un seul sur 5, 6 et parfois 8...

@+


Arx Tarpeia Capitoli proxima...

Hors ligne

#5 26-09-2020 09:12:23

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

Re : Génération des nombres premiers : algorithme

ok , il t"en rajoute 33 .

Bonjour @Yoshi, je te laisse la main ....

J'attends ton idée de reprogrammation de notre algorithme ....déjà pour Ératosthène ou Goldbach et/ou: pour la fusion des deux ... le crible_EG2_mod30 c'est celui ci qu'il faudrait optimiser, afin de vérifier assez loin le nombre de représentation R(n) de 2n en somme de deux nombres premiers p+q pour une limite n fixée.
avec n= 15k + i , soit :  2n =30k + 2i.
@+

Dernière modification par LEG (26-09-2020 09:20:17)

Hors ligne

#6 26-09-2020 09:14:40

Omhaf
Membre
Inscription : 16-01-2020
Messages : 38

Re : Génération des nombres premiers : algorithme

Mon horizon est limité oui c'est vrai
Désolé d'avoir perturbé

Hors ligne

#7 26-09-2020 14:28:00

Omhaf
Membre
Inscription : 16-01-2020
Messages : 38

Re : Génération des nombres premiers : algorithme

Dernière chose à mentionner avant de me taire
tout le monde sait confectionner un algorithme
Boucle allant de 1 a X
vérifier dans une autre boucle allant de  2 à racine de X
vérifier si la division donne un reste nul ou non (modulo)
afficher si reste différent de  0 (c'est un nombre premier)

Quant à ma méthode elle diffère totalement et procède avec une nouvelle logique qui n'a pas besoin de boucler et reboucler
Pas Grave

Hors ligne

#8 26-09-2020 15:11:11

yoshi
Modo Ferox
Inscription : 20-11-2005
Messages : 15 084

Re : Génération des nombres premiers : algorithme

Cher ami,

On te dirait fâché... ?
C'est l'expression "horizon limité" qui te chagrine ?
Alors, laisse-moi t'expliquer :
avec le langage Python, je peux manipuler des nombres entiers de 30 000 chiffres sans souci...
Est-ce que tu peux le faire, toi ?
Sans ce langage, moi, je ne peux pas...
Donc, Python me permet des calculs plus imposants qu'à la main ou qu'avec n'importe quelle calculatrice...
Mon horizon est donc limité à la main ou avec une calculatrice par rapport à l'emploi du langage Python...
C'est plus clair ?

Si tu as pris l'expression comme une insulte ou visant à te faire passer pour quelqu'un à l'intelligence limitée, tu t'es trompé complètement.

Par contre, je suis un peu déçu de ne pas avoir vu de commentaire (pas seulement le mien) à propos des réponses à ta discussion sur les sommes de carrés : là aussi quelque chose t'aurait vexé ?

Quant à ma méthode elle diffère totalement et procède avec une nouvelle logique qui n'a pas besoin de boucler et reboucler

Si tu tiens à protéger ta découverte, alors écris-la sur une feuille de papier que tu dates, signes et que tu fais authentifier par un huissier.
Tu la déposes ensuite dans un coffre  à la banque.
Enfin, cela fait, reviens s'il te plaît et explique-nous ton algorithme afin qu'on puisse voir en quoi il pose un problème pour pouvoir y remédier.

A te lire.

@+


Arx Tarpeia Capitoli proxima...

Hors ligne

#9 26-09-2020 16:37:45

48PierrelePetit
Membre
Inscription : 17-09-2020
Messages : 49

Re : Génération des nombres premiers : algorithme

Bonjour au Forum

Un petit programme Visual Basic qui donne en quelques minutes le premier million des nombres premiers dans leur ordre naturel sous EXCEL.

Sub Macro1()

          Dim p(1000000)
          p(1) = 2: Cells(1, 1) = 2
          p(2) = 3: Cells(2, 1) = 3
          n = 2: l = 3
          c = 1
          For i = 7 To 10 ^ 14 Step 2
          x = i ^ 0.5
          For j = 2 To n
          If p(j) * Int(i / p(j)) = i Then GoTo 10
          If p(j) > x Then GoTo 5
          Next j
5         n = n + 1
          p(n) = i
          Cells(l, c) = i
          l = l + 1
          If l > 50000 Then l = 1: c = c + 1: Cells(l, c + 1).Select
          If n > 999999 Then End
10        Next i
          End Sub

Hors ligne

#10 26-09-2020 18:46:31

yoshi
Modo Ferox
Inscription : 20-11-2005
Messages : 15 084

Re : Génération des nombres premiers : algorithme

Bonsoir,

Le crible utilisé par LEGécrit en Python sur ma machine qui n'est pas une bête de course mais 16 Go RAM :
- le millionième premier est 15 485 863
- temps de calcul 6,2 s  (un vrai TGV)
- je tape assez large avec $16 \times 10^6$
je sors à 1000000 de premiers

Si je ne le bride pas, avec n = 16000000
- j'obtiens 1 031 130 premiers
- le 1 031 130e est 15 999 989
- temps : 5,2 s

@+


Arx Tarpeia Capitoli proxima...

Hors ligne

#11 26-09-2020 21:07:19

48PierrelePetit
Membre
Inscription : 17-09-2020
Messages : 49

Re : Génération des nombres premiers : algorithme

Bonsoir yochi et au Forum
Je me suis senti obligé de donner une réponse précise à la question de Omhaf.
Avec la commande pfgw64 -od -qp(200000000) ( programme pfgw64 installé sur mes PC ) pfgw programme développé par primeform group.
j'obtient en moins d'une seconde chrono 4222234441 pour le 200 millionième nombre premier et pareil pour tout grand nombre premier.
Tout est possible si d'autres que vous ont travaillé pour mettre au point des outils qui n'existaient pas avant eux et que nous utilisons .
Il faut les remercier et en profiter si vous voulez progresser et je m'inclinerait toujours devant celui qui m'apprend quelque chose que je ne ne connaissais pas, à toi de m'apprendre quelque chose de nouveau pour moi et je m'inclinerai.
Merci pour ton intervention et bonne soirée et bonne nuit à tous.

Hors ligne

#12 27-09-2020 09:56:15

yoshi
Modo Ferox
Inscription : 20-11-2005
Messages : 15 084

Re : Génération des nombres premiers : algorithme

Bonjour,

Avec la commande pfgw64 -od -qp(200000000) ( programme pfgw64 installé sur mes PC ) pfgw programme développé par primeform group.

Je ne parle pas de programme professionnel : comparons ce qui est comparable.
J'ai utilisé le langage Python ; dans ce langage, j'ai contribué à optimiser le programme utilisé par LEG.
Python est un langage interprété et haut niveau, pas compilé, donc lent.
Python est un langage libre et gratuit.
Nous ne sommes pas de programmeurs de métier.
En ce sens, le petit bout de script que j'utilise "jouait dans la même cour" que ta macro en VB : il ne peut se comparer avec ce que tu cites.

Je ne vais pas comparer les performances du SCENIC 135 ch de mon voisin avec celles d'une Ferrari !!!
Sachons raison garder ...
Si je récris le script en C et que je le compile j'irai 20 à 30 fois plus vite avec la même machine, sans pouvoir arriver à la cheville de ton pfgw64...
Le script Python en question :

from time import time

def candidate_range(n):
    cur = 5
    incr = 2
    while cur < n+1:
        yield cur
        cur += incr
        incr ^= 6  

def ERA(n):  
    prime_list = [2, 3]
    sieve_list = [True] * (n+1)
    for each_number in candidate_range(n):
        if sieve_list[each_number]:
            prime_list.append(each_number)
            for multiple in range(each_number*each_number, n+1, each_number):
                sieve_list[multiple] = False
    return [2,3,5]+prime_list[3:]

debut=time()
P=ERA(16*10**7)
print(len(P))
print(P[-1])
print(time()-debut)

Tout est possible si d'autres que vous ont travaillé pour mettre au point des outils qui n'existaient pas avant eux et que nous utilisons .

(...) nous utilisons.(...)
Nous ? Que voilà un pluriel bien... singulier (puisque le pluriel de majesté n'est plus en usage depuis longtemps.
Es-tu ici le VIP d'une S informatique ?

@+


Arx Tarpeia Capitoli proxima...

Hors ligne

#13 27-09-2020 12:59:03

48PierrelePetit
Membre
Inscription : 17-09-2020
Messages : 49

Re : Génération des nombres premiers : algorithme

Bonjour yoshi et à tout le Forum
Nous utilisons tous des outils conçus par d'autres que nous à ton exception peut-être si tu es le créateur  de Python !
J'ai programmé en Fortran, en A P L, en Pascal, en langage machine sur le processeur 8 bits,en Basic, en Visual Basic en Script ( utilitaire de PFGW comparable au Basic ) et suis  disponible pour utiliser tout nouveau langage plus efficace en performances que ceux que j'utilise ou qui sont utilisés par ceux qui y trouve un outil qui leur convient dans la mesure ou il est libre et ouvert à tous gratuitement.
En ce qui concerne PFGW ce n'est pas un programme professionnel comme tu le dis, c'est le résultat d'un travail de groupe qui est ouvert à tous librement et gratuitement et que tu pourras retrouver facilement en cherchant sur le net.
Bonne journée à tous

Dernière modification par 48PierrelePetit (27-09-2020 15:46:06)

Hors ligne

#14 28-09-2020 08:38:02

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

Re : Génération des nombres premiers : algorithme

Bonjour
@48PierrelePetit
Ce que dit @Yoshi concernant mon algorithme qu'il a programmé en python , il a aussi été programmé en C++..
Et effectivement les limites et temps de calcul ne sont pas comparable, pour une limite $n = (4 222 234 441 + 29)$ ou pour $2n$ concernant le deuxième algorithme qui donne le nombre de nombres premiers entre $n\: et\: 2n$,

pour info pour $n$ la limite de ton nombre premier 4 222 234 441 + 29 , il y a 24 999 915 nombres premiers de la forme 30k + 1 en 0,4 secondes... tu vois que le programme de mon algorithme, python de Yoshi, retranscrit en C++, n'est pas comparable.

et pour cette même limite $n$ il nous indique aussi qu'il y a 23 407 452 nombres premiers de la forme 30k + 1 entre 4 222 234 460 et 8 444 468 920 en 0,4 secondes ...

Tu peux vérifier que le programme en question se trouve sur le forum programmation  à la page 15 : http://www.bibmath.net/forums/viewtopic … 10154&p=15

Mais ta réponse est intéressante, pourrais tu me retranscrire en C++ et en utilisant les slices comme ce la a été fait dans le programme en question . le programme python que @Yoshi m'a fait :

Si besoins je peux mettre les deux programmes en C++ pour les fusionner en C++ , comme il me l'a fait en Python ci dessous, ce qui ferait gagner du temps pour la fusion en C++ .


from time import time
from os import system

def candidate_range(n):
    cur = 5
    incr = 2
    while cur < n+1:
        yield cur
        cur += incr
        incr ^= 6  # or incr = 6-incr, or however

def eratostene(n):
    n1,n = int(n**0.5), int((2*n)**0.5)  #(si on fusionne les deux cribles il faudra rentrer, int((2n)**0.5) pour Goldbach.
    prime_E,prime_EG=[2,3],[]
    sieve_list = [True for _ in range(n+1)] # c'est plus propre comme ça)
    for each_number in candidate_range(n):
        if sieve_list[each_number]:
            if each_number>n1:
                prime_EG.append(each_number)
            else:
                prime_E.append(each_number)
            for multiple in range(each_number*each_number, n, each_number):
                sieve_list[multiple] = False
    #print(prime_E,prime_EG)            
    return prime_E[3:],prime_EG


def Criblage_EG(Premiers,Premiers_suite, n, fam):
    start_crible = time()
    # On génère un tableau de n//30 cases rempli de 1
    lencrible = ((n//30)+1)
    crible=[1 for _ 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
    Premiers+=Premiers_suite
    del Premiers_suite # suppression du tableau devenu inutile
    nbpremiers = len(Premiers)
    n2 = 2*n
    for premier in Premiers:
        reste = n2 % premier
        if reste % 2 == 0:
            reste += premier
        pi2 = 2*premier
       # tant que reste % 30 != fam on fait reste += pi2
        while reste % 30 != fam:
            reste += pi2
        # Ensuite on divise reste par 30 pour obtenir l'index
        reste //= 30
        # On crible directement avec l'index
        for index in range(reste, lencrible, premier):
            crible[index] = 0
    total = sum(crible)
    #print(nbpremiers)
    #print("crible:", crible)
    print(f"Nombres non congru 2n[pi] {1} à {n} famille {fam} premiers de {n} à {n2}: {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 à √n et de √n à √2nN
    Premiers_E,Suite_E = eratostene(n)
    # On crible
    fam = 7 # ou 11, 13, 17, 19, 23, 29, 31 au choix
    Criblage_EG(Premiers_E,Suite_E, n, fam)
   
main()
system("pause")
 

Dernière modification par LEG (30-09-2020 08:18:26)

Hors ligne

#15 28-09-2020 13:07:54

Wiwaxia
Membre
Lieu : Paris 75013
Inscription : 21-12-2017
Messages : 126

Re : Génération des nombres premiers : algorithme

Bonjour,

yoshi a écrit :

... Le crible utilisé par LEGécrit en Python sur ma machine qui n'est pas une bête de course mais 16 Go RAM :
- le millionième premier est 15 485 863
- temps de calcul 6,2 s  (un vrai TGV)
- je tape assez large avec $16 \times 10^6$
je sors à 1000000 de premiers ...

Je ne résiste pas à la tentation de tester le temps d'exécution d'un petit programme rédigé en Pascal:
6 secondes environ, pour trouver la réponse à la même question (15 485 863).
Je triche en partant du 4me nombre premier (7), et en limitant la recherche aux entiers de la forme n = 6k ± 1 .


 PROGRAM Nprem_RangN;

 USES Crt, E_Texte;

 CONST Prem4 = 7; Rang7 = 4; RangMax = 1000000;

 VAR Np, Rp: Z_32;

 PROCEDURE Aff_NpRp;
   CONST C1 = 5; L1 = 5; o = 9;
   BEGIN
     E(1015); Wt(C1, L1 - 1, 'Nombre premier:   Np = ');
     E(0012); Write(Np:o);
     E(0015); Wt(C1, L1 + 1, 'Rang:             Rp = ');
     E(0010); Write(Rp:o); A_
   END;

 FUNCTION TestPrim(VAR N_: Z_32): Bool;
   VAR DeltaQ, q, Rn: Z_32; Test: Bool;
   BEGIN
     q:= 1; DeltaQ:= 4; Rn:= Trunc(Sqrt(N_)); Test:= False;
     REPEAT
       Inc(q, DeltaQ); DeltaQ:= 6 - DeltaQ; Test:= ((N_ MOD q)=0)
     UNTIL ((q>Rn) OR Test);
     Result:= (NOT Test)
   END;

 PROCEDURE Enumeration(VAR P_, R_: Z_32);
   VAR DeltaP, k, p: Z_32;
   BEGIN
     p:= Prem4; k:= Rang7; DeltaP:= 4;
     REPEAT
       Inc(p, DeltaP); DeltaP:= 6 - DeltaP;
       IF TestPrim(p) THEN Inc(k);
     UNTIL (k=RangMax);
     P_:= p; R_:= k
   END;

 BEGIN
   Enumeration(Np, Rp);
   Aff_NpRp
 END.

Dernière modification par Wiwaxia (28-09-2020 13:12:54)

Hors ligne

#16 28-09-2020 13:52:47

yoshi
Modo Ferox
Inscription : 20-11-2005
Messages : 15 084

Re : Génération des nombres premiers : algorithme

Bonjour,

Je vais me répéter...
Python est langage interprété, haut niveau, donc peu rapide...

Je précise :
quand j'ai écrit : un vrai TGV, je comparais la vitesse d'exécution de ce script avec d'autres sur le même sujet, écrits en Python et non avec le langage tartempion...
Seule dérogation : lorsque j'ai comparé le temps mis par ce script Python avec le script de Pierre-le-Petit en Visual Basic, programme réputé - à juste titre - plus rapide que Python, parce que le temps annoncé (plusieurs minutes) m'avait surpris

Python est lent, certes, mais je l'apprécie pour sa clarté, pour la palanquée de bibliothèque tierces présentes en natif ou installables, sa lisibilité satisfaisante même pour quelqu'un qui ne connaît pas le langage...
Petit bémol : son parti pris de "typage dynamique" qui, à cause de sa souplesse, oblige à faire encore plus attention aux types et aux noms de variables...

Je rectifie ce qu'a dit LEG : je n'ai fait qu'optimiser (j'avais divisé par 30 la vitesse de travail), un script existant, je ne l'ai pas écrit. A partir de quoi, il a été modifié, anglicisé à outrance, ce qui me colle des boutons au point que j'ai renoncé à en comprendre les modifications...
Je sais, ce n'est pas bien, mais on se refait pas... ^_^

@+


Arx Tarpeia Capitoli proxima...

Hors ligne

#17 28-09-2020 14:30:25

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

Re : Génération des nombres premiers : algorithme

Bonjour

===== RESTART: E:\Documents\Conjecture de Goldbach\Crible_ Era_gty_mod30.py ====
Donnez N: 16000000
Nombre premiers criblés famille 13 : 128937 ----- 0.07
--- Temps total: 0.09 sec ---
>>>

Ce programme @Yoshi, à la base il était était archaïque ...toi tu l'as refait entièrement à partir de l'algorithme ....

Tout comme celui que j'ai mis ci-dessus qui donne le nombre de couples P+q = 2n ...c'est quand même toi qui me l'a fait intégralement en python ...

En définitive ce qui est long c'est d'écrire tous les nombres premiers criblé < n fixé et non de calculer leur nombre .

Ensuite il est clair que certain algorithme et programme sont très rapide en fonction du langage, de la complexité de l'algorithme, du calculateur ou Pc utilisé..

ex : le 400 milliardième premier est : The 400,000,000,000th prime is 11,618,595,583,891; en moins de 1,5 secondes et je suppose qu'il y a plus rapide...

Bref disait moi et non Pépin ... @Wiwaxia ou 48PierrelePetit y'en a t'il un, pour retranscrire en C++ le crible en python que j'ai mis  ci-dessous... si possible bien entendu...

Actuellement pour n = 16 000 000 000 il me donne :

======= RESTART: E:\Documents\Conjecture de Goldbach\Crible_EG2_mod30.py =======
Donnez n: 16000000060
Nombres P' non congruent à [pi] de 1 à 16000000060 famille 7, nombr de couples p+q=2n: 15 133 152 ----- 227.22 secondes
>>>
Donnez n: 16000000075
Nombres P' non congruent à [pi] de 1 à 16000000075 famille 7, nombr de couples p+q=2n: 14 349 243 ----- 211.01

Donnez n: 16000000090
Nombres P' non congruent à [pi] de 1 à 16000000090 famille 7, nombr de couples p+q=2n: 13 131 524 ----- 213.3
>>>


Avec les nombres premiers Pn et qn : Pn = 30k+7 et qn = 30k +13

En utilisant la fonction modifiée $\pi(n)$ pour le nombre de premiers 30k +7 et la constante des nombres premiers jumeaux $C_2$ :
Nombre de premiers $30k + 7  < 16000000030 = 89 101 240$
l'estimation me donne 6 426 691 couples qui représentent $2n = 32 000 000 060$ en somme de deux nombres premiers p+q .

Pratiquement la moitié du nombre réel de couples p+q ... Ce qui est quand même très curieux,  car il suffit de multiplier par 2 le résultat de la fonction d'estimation pour obtenir une moyenne générale ...

La fonction est : pour un nombre de nombre premiers de la forme de $30k + i$ ; $i\in(1,7,11,13,17,19,23,29)$ et une limite fixée : $n = 15k + i$

$\frac{\pi(n)}{ln\:(\pi(n))}$ sachant aussi que cette fonction indiquera le nombre de couples qui représenteront la limite suivante 2n + 30 sans avoir le besoins de cribler car la fonction est réccurente...

Elle représente aussi le nombre d'entiers A pas obligatoirement premiers de la forme 30k +7 en progression arithmétique de raison 30, non congrus modulo P : $(2n+30)\not\equiv{A}[P]$ avec $P\leqslant\sqrt{2n+30}$

Si on prend les trois limites $n$ suivante on aura une moyenne de 14 204 639 couples = 2n ; pour une estimation de 12 853 383 .

======= RESTART: E:\Documents\Conjecture de Goldbach\Crible_EG2_mod30.py =======
Donnez n: 16000000105
Nombres P' non congruent à [pi] de 1 à 16000000105 famille 7, nombr de couples p+q=2n: 13 467 806 ----- 210.81
>>>
======= RESTART: E:\Documents\Conjecture de Goldbach\Crible_EG2_mod30.py =======
Donnez n: 16000000120
Nombres P' non congruent à [pi] de 1 à 16000000120 famille 7, nombr de couples p+q=2n: 14 334 132 ----- 243.58
>>>
======= RESTART: E:\Documents\Conjecture de Goldbach\Crible_EG2_mod30.py =======
Donnez n: 16000000135
Nombres P' non congruent à [pi] de 1 à 16000000135 famille 7, nombr de couples p+q=2n: 16 239 823 ----- 186.15
>>>
Comme quoi ce crible / algorithme de Goldbach par famille $30k + i$, cache bien des choses...

Dernière modification par LEG (28-09-2020 16:44:16)

Hors ligne

#18 28-09-2020 15:40:22

48PierrelePetit
Membre
Inscription : 17-09-2020
Messages : 49

Re : Génération des nombres premiers : algorithme

Bonjour à tous.
A chacun ses programmes mais comme disait Albert tout est relatif.
J'ai testé le programme suivant en utilisant PFGW64 qui fonctionne sous DOS pour Windows.
Le programme est écrit dans un fichier pro.txt et la commande sous DOS est pfgw64 pro.txt.

SCRIPT
DIM i,0
DIM j,100000000-1
DIM x
SET x,p(100000000)
PRINT x
LABEL boucle
SET j,j+1
IF p(j)%30==1 THEN SET i,i+1
IF i==1000 THEN SET x,p(j)
IF i<1000 THEN GOTO boucle
PRINT j
PRINT x

Qui donne après 14 minutes et 35 secondes les réponses suivantes :
2 038 074 743 pour p(100 000 000)
p(100 007 813)=2038242961 et sur les 7814 premiers 1000 sont 1 modulo 30
Le même programme à une puissance de 10 inférieure donne après une minute et 45 secondes :
179 424 673 pour p(10 000 000) et p(10 008 340)=179 583 301 et 1000 premiers 1 modulo 30 sur les 8341.
Enfin en réduisant encore d'une puissance de 10, on obtient en 17 secondes p(1 000 000)=15 485 863, p(1 008 068)=15 618 061 et 1000 premiers 1 modulo 30 sur les 8069 premiers.
Cela semble donner une proportion moyenne de premiers 1 modulo 30 de 1/8, et aussi 1/8 pour les -1 modulo 30,     
Merci à tous et bonne journée

Hors ligne

#19 28-09-2020 15:50:50

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

Re : Génération des nombres premiers : algorithme

@48pierrelePetit

Cela semble donner une proportion moyenne de premiers 1 modulo 30 de 1/8, et aussi 1/8 pour les -1 modulo 30,     
Merci à tous et bonne journée

C'est normale il y a 8 familles de nombre premier >5 ,  de la forme 30k + i
Et comme l'algorithme qui crible ses 8 familles avec le même nombre de nombre premiers P inférieur à racine de n, est le même; tu as par conséquent une densité moyenne de 1/8 par famille .

Hors ligne

#20 28-09-2020 17:07:07

Wiwaxia
Membre
Lieu : Paris 75013
Inscription : 21-12-2017
Messages : 126

Re : Génération des nombres premiers : algorithme

@ 48PierrelePetit

Bonjour,

48PierrelePetit a écrit :

... Avec la commande pfgw64 -od -qp(200000000) ( programme pfgw64 installé sur mes PC ) pfgw programme développé par primeform group, j'obtiens en moins d'une seconde chrono 4222234441 pour le 200 millionième nombre premier et pareil pour tout grand nombre premier ... / ...
J'ai testé le programme suivant en utilisant PFGW64 qui fonctionne sous DOS pour Windows.
Le programme est écrit dans un fichier pro.txt et la commande sous DOS est pfgw64 pro.txt.
... / ...
Qui donne après 14 minutes et 35 secondes les réponses suivantes :
2 038 074 743 pour p(100 000 000)

Il semble qu'il y ait une incohérence dans les délais de calcul annoncés, à moins que quelque chose ne m'ait complètement échappé dans la détermination du nombre premier de rang (N)... Peut-être s'agit-il de deux algorithmes différents ?

La première donnée incite à se documenter à fond sur le logiciel en cause !

Dernière modification par Wiwaxia (28-09-2020 17:30:10)

Hors ligne

#21 28-09-2020 17:41:19

48PierrelePetit
Membre
Inscription : 17-09-2020
Messages : 49

Re : Génération des nombres premiers : algorithme

Bonsoir
C'est effectivement l'utilisations de deux fonctions différentes ( et d'autres possibles )
pfgw64 -od -qp(200000000) en ligne de commande directe répond en moins d'une seconde 4222234441
-od pour obtenir à l'écran le résultat et -q pour la fonction à calculer, la fonction p(i) calcule prime(i)
Le programme SCRiPT lui calcule et donne les résultats à l'écran (ou on peut inclure dans le programme la sauvegarde de tous les résultats sur fichier), plusieurs milliers de nombres à 9 ou plus de 9 chiffres d'où les 14 minutes 35 secondes.
Je peux envoyer à qui le souhaite le programme et sa documentation
A plus

Dernière modification par 48PierrelePetit (28-09-2020 18:17:09)

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)?
quatre-vingt huit moins quatre-vingt cinq
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