Demande conseil pour python

LEG · April 2018

Bonjour
j'ai un petit programme en python que j'ouvre avec Pycharm.

import os
from math import*
def main():
    k = 3
    Pi = [7,11,13,17,19,23,29,31,37,41,43,47,53]
    limite = int(input("Quelle valeur limite pour k ?"))
    while k <= limite:
        ss = 30*k
        s = int(sqrt(ss))
        Pp = [31,29,23,19,17,13,11,7]
        Ptemp = []
        reste = []
        r = 0
        i = 0

        #Selection des 1ers
        while Pi[ i] <= s:
            Ptemp.append(Pi[ i])
            i = i+1

        #calcul des restes de bases
        lenPtemp = len(Ptemp)
        j = 0
        for i in range(lenPtemp):
            r = ss%Ptemp[ i]
            if r <= 31:
                reste.append([])
                reste[j].append(r)
                j = j+1

        #completion du tableau de reste
        lenreste = len(reste)
        for i in range(lenreste):
            j = 0
            while reste[ i][j] <= 31-Ptemp[ i]:
                reste[ i].append(reste[ i][j]+Ptemp[ i])
                j = j+1

        #calcul des nombres 1ers
        lenPp = len(Pp)
        for i in range(lenPp):
            ok = 1
            for j in range(lenreste):
                lenrestei = len(reste[j])
                for l in range(lenrestei):
                    if reste[j][l] == Pp[ i]:
                        ok = 0
            if ok == 1:
                Pi.append(ss-Pp[ i])
        k = k+1
    print("Nombres premiers:",Pi)
main()
os.system("pause")

pour le lancer je clic sur le petit icône ( [python] nombres.premiers=1) dans mon répertoire

Mais il m'ouvre une fenêtre dos ,, où il me demande : qu'elle valeur pour K

je rentre 30 ; ("k est un multiple de 30") et il extrait dans cette fenêtre les nombres premiers ce qui est gênant car la fenêtre et trop petite....

comment je dois faire:
1) pour le lancer dans la console python afin qu'il m'écrive les nombres premiers < k fixé, dans cette console en dessous du programme et non dans la fenêtre dos...?
Merci ...

[Mettre une ' ' entre [ et i sinon, l'afficheur du forum le prend pour une bannière BBcode de mise en italique. AD]

Rescassol · April 2018

Bonjour,

J'ai une erreur à la ligne 17, ce qui est normal:

while Pi <= s:

Pi est un liste alors que s est un entier, ça ne peut pas fonctionner.

Cordialement,

Rescassol

Math Coss · April 2018

Quelle valeur limite pour k ?30
Traceback (most recent call last):
  File "tutu.py", line 52, in <module>
    main()
  File "tutu.py", line 49, in main
    Pi.append(ss-Pp)
TypeError: unsupported operand type(s) for -: 'int' and 'list'

En effet, ss est un entier et Pp est une liste (de nombres premiers sans doute ?).

LEG · April 2018

attention :
Pp est la liste des 8 nombres premiers qui permettent d'extraire les nombres premiers > 53.

Pi sont les nombres premiers $<\sqrt{ss}$ et ss et la limite du crible de la forme 30k, k entier naturel >3.

Donc Pi sont les modulo .Le crible vérifie si Pp [7 ; 31] est congru à 30k [Pi], il progresse par pas de 30.

par exemple: si SS = 900
Pi $<\sqrt{900}$ donne les Pi {7,11,13,17,19,23, et 29} inférieur à 30..

ne sont pas congrus à 900[Pi] : {13,17,19, et 23} qui donneront donc 4 nombres premiers entre 870 et 900, soit :
900 -13 ; 900 -17 ; 900 - 19 ; et 900 - 23.

extrait:
["[b]23 19 17 13[/b]" 11 7 31 29]
["[b]877 881 883 887[/b] 0 0 0 0" ]

les 8 Pp sont les 8 nombres premiers de base, qui permettent le criblage principe et variante d'Eraosthène , dans les congruences...

mais souci n'est pas le fonctionnement du crible , mais je voudrait faire apparaître les nombres premiers en dessous dans la [console Python] et pouvoir le lancer dans Pycharm...ce qui est plus facile pour faire un copie collé ensuite , car dans la petite fenêtre "dos" ou " cmd" je ne vois pas tous les nombres....

je ne sais pas programmer, c'est mon petit fils qui a fait le programme et qui est actuellement à Chicoutimi Québec jusqu'en septembre...voila voili...8-)

Je ne sais pas ce que je dois faire avec vos deux messages....@Rescassol et Math cross...

Est ce qu'il faut que je remplace la ligne 49 et 52 dans Pycharm...?? car si j'écris la ligne 49 comme ceci :

Pi.append(ss-Pp)

ça ne marche pas....

voici un extrait de la fenêtre cmd

Quelle valeur limite pour k ? je rentre 30 résultat:
Nombres premiers: [7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67
, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151,
157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239,
241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337,
347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433,
439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541,
547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641,
643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743,
751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857,
859, 863, 877, 881, 883, 887]
Appuyez sur une touche pour continuer...

Rescassol · April 2018

Bonsoir,

Ah ben, ça marche maintenant, je suppose que la correction de AD a supprimé le problème.
Et dans Pyzo (je ne connais pas Pycharm), j'obtiens bien la même chose que toi dans cmd.

Cordialement,

Rescassol

LEG · April 2018

@Rescassol
le programme il marchait, c'est que simplement je voulais lancer l'application dans la console python de Pycharm... au lieu de cmd; j'ai trouvé comment avec le clic droit dans cmd, je pouvais changer les paramètres de la fenêtre, afin de l'agrandir et de faire un copier coller des entiers premiers mais la fenêtre se ferme facilement en cliquant sur ctrl.c , ... voilà.

Je voulais voir avec un autre programme qui utilise Eratosthène pour extraire les nombres premiers $P_i <\sqrt{2N}$ si c'était plus simple de faire appel à une base de données dans un répertoire que le programme va ensuite ouvrir pour allez chercher les $P_i$.

On prend en exemple : le répertoire des $P_i< 900$ où $900$ est la racine carrée de $2N = 30k$
Nombres premiers Pi: [7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53,
137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199
283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373
461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557
643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733
829, 839, 853, 857, 859, 863, 877, 881, 883, 887]

programme: crible_mod30
extrait:
Donnez la valeur de N = 30k : 810000
Crible mod30 : Initialisation: 0.031199932098388672 seconds ---
Crible mod30 : Famille de chaque Pi: 0.20280027389526367 seconds ---
Crible mod30 : Criblage des 8 familles: 0.031200170516967773 seconds ---
Crible mod30 : Extraction des premiers: n à 2*n : 0.015599966049194336 seconds ---
On a 57857 nombres premiers
Appuyez sur une touche pour continuer...

Voici le programme:

import os
import math
import time

def eratostene(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

# On travaille avec 8 familles (1, 7, 11, 13, 17, 19, 23, 29)
# ATTENTION: n doit être multiple de 30
def crible_mod30(n):
	# INITIALISATION
	start_time = time.time()
	nbcell = int(n/30)
	nombres = [[1 for _ in range(nbcell)] for _ in range(8)]
	p = eratostene(int(n))
	p = p[3:]
	lenp = len(p)
	r = []
	p8 = [1, 7, 11, 13, 17, 19, 23, 29]
	pfam = []
	print("Crible mod30 : Initialisation: %s seconds ---" % (time.time() - start_time))

	# FAMILLES POUR CHAQUE Pi
	start_time = time.time()
	for i in range(lenp):
		r.append(2*n % p[ i])
		pfam.append([0, 0, 0, 0, 0, 0, 0, 0])
		j = r[ i]
		incr = p[ i]*2
		d_c = str(j)[-1]
		# si la terminaison du reste est pair on ajoute directement Pi et on verifie
		if d_c in ['0','2','4','6','8']:
			j += p[ i]
			d_c = str(j)[-1]
		while j < n:
			if d_c == '5' or j % 3 == 0:  # on passe au suivant
				fam = -1
			elif d_c == '1':  # on vérifie 1 et 11
				if j % 30 == p8[0]:
					fam = 0
				else:
					fam = 2
			elif d_c == '3':  # on vérifie 13 et 23
				if j % 30 == p8[3]:
					fam = 3
				else:
					fam = 6
			elif d_c == '7':  # on vérifie 7 et 17
				if j % 30 == p8[1]:
					fam = 1
				else:
					fam = 4
			else:  # on vérifie 19 et 29 (d_c = 9)
				if j % 30 == p8[5]:
					fam = 5
				else:
					fam = 7
			if fam != -1 and pfam[ i][fam] == 0:
				pfam[ i][fam] = j
			j += incr
			d_c = str(j)[-1]

	print("Crible mod30 : Famille de chaque Pi: %s seconds ---" % (time.time() - start_time))

	# ON CRIBLE LES 8 COLONNES AVEC CHAQUE FAMILLE DE Pi
	start_time = time.time()
	lenpfam = len(pfam)
	for i in range(lenpfam):
		for j in range(8):
			index = int((pfam[ i][j] - p8[j]) / 30)
			while index < nbcell:
				nombres[j][ index] = 0
				index += p[ i]
	print("Crible mod30 : Criblage des 8 familles: %s seconds ---" % (time.time() - start_time))

	# AFFICHAGE
	for i in range(8):
		count = 0
		for cell in nombres[ i]:
			if cell == 1:
				count += 1

	# CALCUL DES NOMRES PREMIERS ENTRE N ET 2*N
	start_time = time.time()
	premiers = []
	for i in range(8):
		for j in range(nbcell-1, -1, -1):
			if nombres[ i][j] == 1:
				premiers.append(nombres[ i][j] == 1)
	print("Crible mod30 : Extraction des premiers n à 2*n : %s seconds ---" % (time.time() - start_time))
	premiers.sort()
	return premiers

n = int(input("Donnez la valeur de N = 30k : "))
nb = len(crible_mod30(n))
print("On a "+str(nb)+" nombres premiers")
os.system("pause")

Donc tu vois la première partie fait appel à Eratosthène....est-ce une bonne chose ??? :-S
De plus il faut le modifier afin qu'il ne travaille que dans une famille, plus simple, plus rapide et irait plus loin..
Là, je suis limité à N = 3 720 000 000 pour connaître le nombre de premiers de N à 2N... qui est :165 910 122
Mon petit fils est au Québec il me faut attendre Octobre ... :)o
Bonsoir...

[Mettre une ' ' entre [ et i sinon, l'afficheur du forum le prend pour une bannière BBcode de mise en italique. AD]

Rescassol · April 2018

Bonsoir,

> Mon petit fils est au Québec il me faut attendre Octobre

Il n'y a pas internet, au Quebec ?

Cordialement,

Rescassol

LEG · April 2018

Bonjour
@Rescassol bien évidemment ; mais il m'a dit qu'il a trop de travail pour ses examens et qu'il préfère que je sois la bas pour lui expliquer exactement ce que je veux , et ensuite on vérifie si tout est ok...
(Peut être qu'il est trop occupé...en ce moment, car effectivement cela va lui prendre une heure ou deux au grand maxi...)

Cordialement.
LG

LEG · April 2018

Bonjour
est-ce qu'il y a une limite dans python, car voici les différentes valeurs de 30k extrait :

=== RESTART: E:\Documents\Conjecture de Goldbach\Crible_G.T.Y_modulo30.py ===
Donnez N: 29400000000
Nombre premiers criblés famille 1 entre 29400000000 et 58800000000: 150069716

181.83
--- Temps total: 183.9 sec ---
>>>
=== RESTART: E:\Documents\Conjecture de Goldbach\Crible_G.T.Y_modulo30.py ===
Donnez N: 30000000000
Nombre premiers criblés famille 1 entre 30000000000 et 60000000000: 153006648 ----- 8560.95
--- Temps total: 8576.72 sec ---

curieux temps mis entre N = 29 400 000 000 et 30 000 000 000...
Est-ce une limite due à Python...???

from time import time
from os import system

## V. 6.3 ##

def eratostene(n):
    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
    return premiers[3:]

def CribleG4Y_mod30(n):
    # INITIALISATION
    global nombres,nbcell
    start_i= time()
    Primes_init=eratostene(n)
    nn,nbcell=n*2,n//30
    nombres=[]
    debut=time()
    for i in range(1):
       nombres.append([1]*nbcell)
    P8={1:0}
    s_1=time()-start_i
    print("Phase d'initialisation: %s seconds ---" % s_1)
   
    # FAMILLES POUR CHAQUE Pi
    start_time = time()
    for i,pi in enumerate(Primes_init):      
       j=nn%pi
       debut,fin,pas=j+pi*(1-j%2),min(pi*30,n),pi*2
       temoin=0
       for j in range(debut,fin,pas):
           if j%30==1:
             fam=P8[1]  # modifier la valeur de la fam à cribler [1,7,11,....,29]
             if not ((1<<fam)&temoin):
                temoin=(1<<fam)|temoin
                debut_index=j//30
                Nombres_fam=nombres[fam]
                for index in range(debut_index, nbcell,pi):
                   Nombres_fam[index]=0
    s_23=time()-start_time
    #print(j)
    print("Bloc S2_s3 : %s seconds ---" % s_23)

    # CALCUL DES NOMRES PREMIERS ENTRE n ET 2*n
    start_time = time()
    total=0
    for sous_liste in nombres:
        total+=sum(sous_liste)      
    s_4=time() - start_time
    s=s_1+s_23+s_4
    print("Extraction des premiers n à 2*n : %s seconds ---" % s_4)
    return total,s

n = int(input("Donnez la valeur de n = 30k : "))
nbr,s= CribleG4Y_mod30(n)
print ("\n** ",nbr,"nombres trouvés en %s secondes" % s ,"**")
system("pause")

crible modifié.

LEG · December 2018

Bonjour @AD

2) Impossible d'éditer ce programme modifié en mettant les balises [ code] [/code] ???

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):
    n = int((2*n)**0.5)
    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
    #print(prime_list)
    return prime_list[3:]


def demander_N():
    n = input("Donnez N: ")
    n = int(n.strip().replace(" ", ""))
    #n = int(30 * round(float(n)/30))
    #print(f"On prend N = {n}  (30 * {int(n/30)})")
    return n


#def lprint(text="", liste=None):
    if len(liste) < 100:
        print(text + str(liste))


def GCrible(premiers, n, fam):
    start_crible = time()
	
    # On génère un tableau de N/30 cases rempli de 1
    crible = n//30*[1]
    lencrible = len(crible)

    # On calcule les restes: ri = 2*n/pi
    nbpremiers = len(premiers)
    n2 = 2*n
	
    for i, premier in enumerate(premiers):
        reste = n2 % premier
	# tant que ri % 30 != fam on fait ri += 2pi
        if reste % 2 == 0:
            reste += premier
        pi2 = 2*premier
        while reste % 30 != fam:
            reste += pi2
        # Ensuite on divise ri par 30 pour obtenir l'indexe
        reste //= 30
        # On crible directement avec l'index
        for index in range(reste, lencrible, premier):
            crible[index] = 0

    total = sum(crible)
    #lprint("crible:", crible)
    print(f"Nombre premiers criblés famille {fam} entre {n} et {n2}: {total} ----- {int((time()-start_crible)*100)/100}")


def main():
    # On demande N a l'utilisateur
    n = demander_N()

    # On récupère les premiers entre 7 et ?2N
    premiers = eratostene(n)
    #lprint("premiers:", premiers)
    #print(f"nombres premiers entre 7 et {int((2*n)**0.5)}: {len(premiers)}")

    start_time = time()
    # On crible
    GCrible(premiers, n, 1)
    temps = time()-start_time
    print(f"--- Temps total: {int(temps*100)/100} sec ---")


main()
system("pause")

Pour changer de Famille modulo 30, il suffit de remplacer la variable 1 de la ligne de programme :
GCrible(premiers, n, 1) par P {7,11,13,17,19,23, ou 29}

lorsque la limite N demandée = 30 000 000 000 , passe de 185 seconde pour N =29 400 000 000 à plus de 8500 secondes ....?
Est ce qu'il faudrait écrire le programme en C++...?

Extrait des temps d'exécution:

=== RESTART: E:\Documents\Conjecture de Goldbach\Crible_G.T.Y_modulo30.py ===
Donnez N: 24000000000
Nombre premiers criblés famille 1 entre 24000000000 et 48000000000: 123530551

127.23
--- Temps total: 128.73 sec ---
>>>
=== RESTART: E:\Documents\Conjecture de Goldbach\Crible_G.T.Y_modulo30.py ===
Donnez N: 27000000000
Nombre premiers criblés famille 1 entre 27000000000 et 54000000000: 138301355

237.18
--- Temps total: 238.91 sec ---
>>>
=== RESTART: E:\Documents\Conjecture de Goldbach\Crible_G.T.Y_modulo30.py ===
Donnez N: 29400000000
Nombre premiers criblés famille 1 entre 29400000000 et 58800000000: 150069716

181.83
--- Temps total: 183.9 sec ---
>>>
=== RESTART: E:\Documents\Conjecture de Goldbach\Crible_G.T.Y_modulo30.py ===
Donnez N: 30000000000
Nombre premiers criblés famille 1 entre 30000000000 et 60000000000: 153006648

8560.95
--- Temps total: 8576.72 sec ---

C'est quand même curieux cet écart de temps....

AD · December 2018

Bonjour LEG

1) "Message supprimé...Comment faut-il faire ?"
Si tu veux supprimer ton message, tu le modifies en ne laissant qu'un petit texte explicatif.
Cependant si quelqu'un y a déjà répondu, c'est alors très incorrect de le supprimer. Il vaut mieux dans ce cas le rayer (4ème bouton au dessus de la fenêtre d'édition) du début à la fin, accompagné éventuellement d'un message explicatif.

2) Comment impossible ? Je viens de le faire. :-S

AD

LEG · December 2018

Re @AD
Ok pour le 1)

mais pour l'édition du programme j'ai essayé à plusieurs reprises ....impossible , il y avait toujours message d'erreur avec tout une page de code......."je retourne pour y ajouter une question"

Merci AD ....

je viens de réessayer voila le message d'erreur:

Phorum Database Error
Sorry, a Phorum database error occurred.
Please try again later!
Error:

donc impossible de l'éditer...:-S
c'est pas grave tu l'as fait...

skilveg · December 2018

Pour le ralentissement des calculs : c'est très vraisemblablement dû au fait que Python stocke les entiers sur une taille mémoire fixée jusqu'à un certain point où il bascule en "entiers longs". Il faudrait creuser dans la doc.

LEG · December 2018

ok @skilveg.

Il ne me reste plus qu'à trouver quelqu'un, qui veut bien me le refaire en C++....et lui payer le restau....:)o
Bonne soirée...

Rescassol · December 2018

Bonsoir,

Qui choisit le restau ?

Cordialement,

Rescassol

LEG · December 2018

Et bien... toi bien sûr....(:P)...

Cordialement
LEG

Rescassol · December 2018

Bonne nuit,

Le "Jardin des Sens" à Montpellier, ça te va ?

Cordialement,

Rescassol

parisse · December 2018

Quelle est la taille de votre RAM ?
Vous allouez dans GCrible une liste crible de n/30 uns avec n/30 de l'ordre de 2 milliards, il est possible que le n limite corresponde au fait de swapper ou non.
À première vue, crible pourrait être une liste de booléens, donc un tel tableau dans un langage efficace devrait occuper 2e9/32 octets soit 62Mo de RAM. Je ne sais pas dans quelle mesure on peut contrôler ça en Python, j'ai bien peur que le moindre 1 ou True occupe 8 octets si ce n'est plus, multiplie par 2 milliards on arrive a 16Go (et peut-être même plus).

LEG · December 2018

Rescassol écrivait:

Le "Jardin des Sens" à Montpellier, ça te va ?

Excellent choix ...C'est le nouveau jardin des sens...?

j'espère que le menu découverte est aussi excellent que le palais des saveurs (la colle sur loup) ou le Toqué à Montréal...

si tu est sérieux , je le suis aussi....

tu as compris le fonctionnement de l'algorithme Goldbach en Python ...? (variante Eratosthène modulo 30).

Mais là, on utilise les congruences..ensuite le principe est identique, au lieu de partir de P_i nombre premier $\leqslant\sqrt 2N$ pour marquer ses multiples par pas de P_i, on part de R_i et on marque ses congruents par pas de P_i...jusqu'à N, limite fixée.

R_i : c'est le reste R de la division Euclidienne de 2N par P_i.
Ses congruents veut dire : les entiers inférieur à N congrus à 2N (modulo P_i).

Donc attention : lorsque l'on crible par ex : la famille 1 (mod30), suite arithmétique de raison 30; jusqu'à N.

On obtient le nombre de nombres premiers de la famille complémentaire; c'est à dire la famille 29 (mod30)...de n à 2n
soit 2n = 30 d'où 30 - 1 = 29....
Ce qui serra identique à Eratosthène si on avait criblé jusqu'à 2n en faisant ensuite une soustraction ....$P_{2n} - P_n$

Dans l'attente du programme et d'un bon repas.:)o... , passe une bonne journée .
Cordialement
Leg

parisse · December 2018

Voila ma version C++, il faut une vingtaine de secondes sur ma machine. On peut sans doute optimiser un peu gcrible en déroulant la boucle.

// -*- compile-command: "/usr/bin/g++ -g goldbach.cc" -*-
#include <vector>
#include <iostream>
#include <cmath>
#include <stdlib.h>
using namespace std;
// fill Erathosthene sieve crible for searching primes up to 2*crible.size()*32+1
// crible is a (packed) bit array, crible[ i] is true if 2*i+1 is a prime
// crible must be set to true at startup
void fill_crible(vector<unsigned> & crible,unsigned p){
  crible.resize((p-1)/64+1);
  unsigned cs=crible.size();
  unsigned lastnum=64*cs;
  unsigned lastsieve=int(std::sqrt(double(lastnum)));
  unsigned primesieved=1;
  crible[0] = 0xfffffffe; // 1 is not prime and not sieved (2 is not sieved)
  for (unsigned i=1;i<cs;++i)
    crible[ i]=0xffffffff;
  for (;primesieved<=lastsieve;primesieved+=2){
    // find next prime
    unsigned pos=primesieved/2;
    for (;pos<cs;pos++){
      if (crible[pos/32] & (1 << (pos %32)))
	break;
    }
    // set mutiples of (2*pos+1) to false
    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){
  // assumes crible has been filled
  ++p;
  if (p%2==0)
    ++p;
  unsigned pos=(p-1)/2,cs=crible.size()*32; 
  if (2*cs+1<=p)
    return -1;
  for (;pos<cs;++pos){
    if (crible[pos/32] & (1<<(pos%32))){
      pos=2*pos+1;
      // if (pos!=nextprime(int(p)).val) CERR << "error " << p << endl;
      return pos;
    }
  }
  return -1;
}

typedef unsigned long long ulonglong;

size_t GCrible(const vector<ulonglong> & premiers,ulonglong n,int fam){
  int cl=clock();
  size_t lencrible=n/30,nbpremiers=premiers.size();
  vector<bool> crible(lencrible,true);
  ulonglong n2=2*n;
  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!=fam)
      reste += pi2;
    reste /= 30;
    for (size_t index=reste;index<lencrible;index+=p)
      crible[index]=0;
  }
  size_t total=0;
  for (size_t index=0;index<lencrible;++index)
    total += int(crible[index]);
  cout << "Nombre premiers criblés famille " << fam << " entre "<< n << " et " << n2 <<": " << total << " time " << (clock()-cl)*1e-6<< endl;
  return total;
}

int main(int argc,char ** argv){
  vector<unsigned> crible;
  ulonglong N;
  int fam=1;
  if (argc>1){
    N=atoll(argv[1]);
    if (argc>2)
      fam=atoi(argv[2]);
  }
  else {
    cout << "Syntaxe " << argv[0] << " N fam. Donnez N puis fam: " ;
    cin >> N;
    cin >> fam;
  }
  double sqrt2N=unsigned(std::sqrt(2*double(N)));
  fill_crible(crible,sqrt2N);
  vector<ulonglong> premiers;
  for (ulonglong p=7;p<=sqrt2N;){
    premiers.push_back(p);
    p=nextprime(crible,p);
    if (p==unsigned(-1)) 
      break;
  }
  GCrible(premiers,N,fam);
}

[Mettre une ' ' entre [ et i sinon, l'afficheur du forum le prend pour une bannière BBcode de mise en italique. AD]

LEG · December 2018

Bonjour
@Parisse

1) attention je ne comprends pas bien le langage de la programmation Python et encore moins C++

2) Il me semble qu'il ne s'agit pas du même crible....?

Alors pour vérifier : prenons en exemple la fam ("famille 1") et limite N = 30 000 000 c'est à dire que l'on va cribler
les entiers congrus à 1 modulo 30 jusqu'à N /30...ok
puisque l'on crible la suite arithmétique 1 de raison 30 avec les $P-i\leqslant\sqrt{2N}$ et donc les $P_i$ appartenant à
[7 ; < 7445] extrait par Eratosthène jusqu'à la racine carrée de N, ("première partie de ton programme)"que l'on va appeler...

pour ensuite cribler à partir de la ligne:

size_t GCrible(const vector<ulonglong> & premiers,ulonglong n,int fam){
  int cl=clock();

le programme calcul l'index, correspondant à l'entier ou $R_i \equiv {1}[30]$ puis on marque les [1] en [0] par pas de $P_i$.....jusqu'à N ...etc etc.

à la fin on compte les [1] qui vont correspondre au nombre de nombre premiers de N à 2N, soit :30 000 000 à 60 000 000.

Voila en exemple avec le prog Python référencé ci-dessus GCrible. le résultat et ref Python 3.7:
......................................................................
Python 3.7.1rc1 (v3.7.1rc1:2064bcf6ce, Sep 26 2018, 15:15:36) [MSC v.1914 64 bit (AMD64)] on win32
Type "help", "copyright", "credits" or "license()" for more information.
>>>
=== RESTART: E:\Documents\Conjecture de Goldbach\Crible_G.T.Y_modulo30.py ===
Donnez N: 30000000
Nombre premiers criblés famille 1 entre 30000000 et 60000000: 213125

0.1
--- Temps total: 0.12 sec ---
>>>
..............................................................................

As Tu le Même résultat pour cette valeur...N = 30méga...?

3)
Pour répondre a ton premier post: j'ai 16 Giga de Ram, et en principe pour N = 30 mds j'ai donc une liste de 1 giga de [1.1.1.......] qui vont être criblés; soit en principe un giga d'octet de ram

4)
je ne pense pas que la limite N demandé par le programme est une limite qui indique de swapper ou non je pense que python le fait tout seul...et que peut être lorsque l'on demande N = 30 000 000 000 , là python va ramer grave...

cela va faire une liste de 1 000 000 000 de 1 à cribler c'est à dire transformer les 1 en 0 par pas de $P_i$ en partant de l'index du reste $R_i$ pour chaque $P_i$.
Cela se traduit : un 1 est un entier non congru à 2N (moduloP_,) , d'où son complémentaire est un nombre premier q de N à 2N.

5)
comment ton programme change la Famille à cribler ...?
est ce la ligne :

int fam =1

on remplace le 1 , {par 7, ou 11 ou ....29}

En tous les cas Merci pour ton dévouement....et pour la suite si cela t'intéresse bien sûr..

parisse · December 2018

J'ai traduit le programme gcrible de Python (la liste des nombres premiers est obtenue par copier-coller du code du crible present dans Xcas). J'ai verifie que le script Python et le programme C++ donnaient le meme resultat, par exemple
./a.out 30000000000 1
Nombre premiers criblés famille 1 entre 30000000000 et 60000000000: 153006648 time 22.34
J'obtiens bien la meme chose que votre script pour N=30000000
Les parametres N et fam sont passes en argument sur la ligne de commande, ou bien demandes a l'utilisateur s'il n'y a pas d'arguments en ligne de commande. Inutile de changer le source, pas besoin de recompiler.

Si vous avez 16Go de RAM, je suis presque sur que la raison du changement de comportement est du au fait que le noyau doit swapper dans la boucle de gcrible (for index in range(reste, lencrible, premiers)...)
En effet la taille du tableau crible correspond, en supposant que l'entier 1 est code sur 8 octets en Python.
Et comme on doit parcourir tout le tableau a chaque iteration de la boucle exterieure, on est tout le temps oblige de swapper le contenu d'une partie de la RAM pour faire place a une autre partie constamment. Or l'acces disque est beaucoup plus lent que l'acces RAM. Phenomene qui ne se produit pas avec le programme C++ car un element du crible occupe 64 fois moins de place.

Si vous avez besoin de plus de vitesse encore, je pense qu'il faut slicer, c'est-a-dire remplir le crible par tranches en creant une boucle exterieure supplementaire. Avec un bon choix de taille de tranche pour que la tranche reste dans le cache L1 du processeur.

LEG · December 2018

Ok Parisse

c'est quand même très très intéressant le résultat 22, secondes pour cribler N = 30 giga ; cela m'intéresse.

jusqu'à qu'elle limite N tu as essayé...?

Comment j'utilise ton programme ...? Dans un exécutable ...? Si oui , est ce que je peux t'envoyer mon adresse Mail par mp...

Les paramètres N et fam sont passés en argument sur la ligne de commande, ou bien demandes a l'utilisateur s'il n'y a pas d'arguments en ligne de commande. Inutile de changer le source, pas besoin de recompiler.

Donc c'est à l'ouverture de l'exécutable, que le programme me demande de rentrer la limite N et de choisir la Fam et j'envoie....C'est ça...?

tu peux tutoyer....Merci pour ton aide A+

brian · December 2018

Bonjour
Il n'est pas très difficile d'implémenter un tableau de bits (compact) en Python 3. Voici une manière de procéder utilisant le type standard bytearray :

import collections

class MyBitArray(collections.abc.Sequence):
    """Tableau de bits implémenté à l'aide d'un bytearray.

    Supporte les protocoles de séquence et d'itérateur ; les valeurs
    sont également modifiables. Chaque valeur retournée par
    __getitem__() est soit l'entier 0, soit l'entier 1.

    Exemple (tableau de 500 valeurs initialisées à 1) :

      t = MyBitArray(500, init=1)
      t[35] = 0             # affectation de la 36e valeur, mise à 0
      t[36] = 1             # affectation de la 37e valeur, mise à 1
      t[-2] = 1             # affectation de l'avant-dernière valeur
      print(t[35])          # affiche la 36e valeur
      print(t[-1])          # affiche la dernière valeur

    """

    def __init__(self, size, *, init=None):
        assert size >= 0, size

        self.size = size
        # Chaque octet (de 8 bits) peut stocker 2**3 = 8 booléens
        self.byteSize = (size >> 3) + 1
        self.array = bytearray(self.byteSize)

        if init is not None:
            self.fill(bool(init))

    def fill(self, value):
        byteVal = 255 if value else 0

        for i in range(self.byteSize):
            self.array[ i] = byteVal

    def __len__(self):
        return self.size

    def _checkIndex(self, index):
        if index < 0:
            if -index > self.size:
                raise IndexError(f"negative index too small: {index}")
            else:
                return index + self.size
        elif index >= self.size:
            raise IndexError(f"index too large: {index}")
        else:
            return index

    def __getitem__(self, index):
        index = self._checkIndex(index)
        # (index & 0b111) == (index % 8)
        shift = index & 0b111
        return (self.array[index >> 3] & (1 << shift)) >> shift

    def __setitem__(self, index, value):
        index = self._checkIndex(index)

        if value:
            self.array[index >> 3] |= 1 << (index & 0b111)
        else:
            self.array[index >> 3] &= (256 + ~ (1 << (index & 0b111)))

        # assert bool(self[index]) == bool(value), (index, self[index], value)

    def __iter__(self):
        """Itère sur 'self'.

        Cette méthode n'est pas nécessaire mais réduit le nombre de
        calculs à faire pour itérer sur la totalité du tableau.

        """
        for blockIdx in range(self.byteSize - 1):
            for shift in range(8):
                yield (self.array[blockIdx] & (1 << shift)) >> shift

        lastBlockIdx = self.byteSize - 1
        for shift in range(self.size % 8):
            yield (self.array[lastBlockIdx] & (1 << shift)) >> shift

Ensuite, il n'y a plus qu'à remplacer dans votre programme

crible = n//30*[1]

par

crible = MyBitArray(n//30, init=1)

Attention, mon code est indenté avec 4 espaces. Pour le coller dans votre fichier, il faudra sans-doute remplacer chaque caractère tabulation de votre fichier par 4 espaces précisément, sinon Python ne va pas aimer (les tabulations, c'est casse-pieds, je préfère les éviter).

Il y a également des gens qui ont écrit des modules specialisés pour ça, en C (voir cette question sur stackoverflow) mais ils ne sont pas dans la bibliothèque standard Python, à ma connaissance. Ces modules sont sans doute plus rapides que l'implémentation ci-dessus, mais au niveau mémoire, ça ne doit rien changer (ou alors, c'est qu'ils utilisent un algorithme de compression, mais ce serait probablement catastrophique pour les performances dans un cas d'utilisation tel que le vôtre).

[Mettre une ' ' entre [ et i sinon, l'afficheur du forum le prend pour une bannière BBcode de mise en italique. AD]

LEG · December 2018

Salut Brian
Là pour moi c'est la brasse coulée ...
Je comprends pour changer dans mon programme le ligne crible = MyBitArray(n//30, init=1).
Mais le reste où est-ce que je le colle ? X:-(
Je suppose au début du programme?
Et qu'ensuite toutes les lignes indentées par tabulation, je les remplace par 4 espaces ?
Le programme c'est mon petit fils qui me l'a fait, il est au Québec... car je suis nul de chez nul , "moi j'ai fait l'algorithme ..."
Le résultat sera-t-il aussi rapide que le programme ci-dessus de Parisse ?

parisse · December 2018

@ LEG : je n'ai pas essayé de voir jusqu’à quelle valeur de N on peut aller. Probablement de l'ordre de 10^12 puisque la taille du tableau de crible dépend linéairement de N. Avec un temps de calcul de l'ordre d'une heure peut-être.

@brian : on va gagner en mémoire, mais le code obtenu sera encore plus lent que le code Python originel qui est déjà environ 10 fois plus lent que le code C++ que j'ai donné (en fait j’étais étonné au 1er abord de ne gagner qu'un facteur 10 environ, jusqu’à ce que je réalise que l'utilisation d'un tableau de bits rend l’accès plus lent car il y a des opérations supplémentaires à faire sur l'index et une lecture en mémoire en plus à chaque écriture dans la boucle de gcrible). Utiliser un langage interprété pour faire un crible efficace ne me semble pas du tout une bonne idée.

LEG · December 2018

@Parisse

donc c'est bon 10^12, même 450 000 000 000 c'est excellent

j'ai un crible Eratosthène modulo 30 ; fait il y a environ 15ans en C++, qui prend N = 450 000 000 000, donc 15 Giga de 1 à cribler, par famille il met environ 2h 20...

("mais ce n'est pas Goldbach et le programme n'a pas respecté certaines instructions de l'algorithme pour aller plus vite, ce n'est pas grave à l'époque cela me suffisait ....")

pour voir la différence avec Python , j'ai essayé tout à l'heure l'exécutable Eratosthène: nbpremier win 32, jusqu'à :
60 000 000 000 voila le résultat en 4 minutes 30:

>Allocation du Tableau en cours...
>Allocation Terminée!
>Calcul du tableau en cours...
>Calcul du tableau terminé!
>Le dernier nombre est:
59 999 999 999
>trouvé à la position:
315 507 135

Pour info: j'ai modifié l'indentation de Gcrible ci-dessus par une indentation 4 espaces...Au cas ou...
je pense qu'il faut garder et utiliser ton crible C++, car les temps d'exécution sont très intéressants...

Dans l'attente de tes instructions...

parisse · December 2018

Voilà le code avec des slices, il est significativement plus rapide, il faut 4 secondes pour 30000000000 et 1 minute pour 450000000000 (450e9)
./a.out 450000000000 1
Nombre premiers criblés famille 1 entre 450000000000 et 900000000000: 2066687454 time 65.9

Mettre une ' ' entre [ et i sinon, l'afficheur du forum le prend pour une bannière BBcode de mise en italique. AD]

// -*- compile-command: "/usr/bin/g++ -g goldbachs.cc" -*-
#include <vector>
#include <iostream>
#include <cmath>
#include <stdlib.h>
using namespace std;
// fill Erathosthene sieve crible for searching primes up to 2*crible.size()*32+1
// crible is a (packed) bit array, crible[ i] is true if 2*i+1 is a prime
// crible must be set to true at startup
void fill_crible(vector<unsigned> & crible,unsigned p){
  crible.resize((p-1)/64+1);
  unsigned cs=crible.size();
  unsigned lastnum=64*cs;
  unsigned lastsieve=int(std::sqrt(double(lastnum)));
  unsigned primesieved=1;
  crible[0] = 0xfffffffe; // 1 is not prime and not sieved (2 is not sieved)
  for (unsigned i=1;i<cs;++i)
    crible[ i]=0xffffffff;
  for (;primesieved<=lastsieve;primesieved+=2){
    // find next prime
    unsigned pos=primesieved/2;
    for (;pos<cs;pos++){
      if (crible[pos/32] & (1 << (pos %32)))
	break;
    }
    // set mutiples of (2*pos+1) to false
    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){
  // assumes crible has been filled
  ++p;
  if (p%2==0)
    ++p;
  unsigned pos=(p-1)/2,cs=crible.size()*32; 
  if (2*cs+1<=p)
    return -1;
  for (;pos<cs;++pos){
    if (crible[pos/32] & (1<<(pos%32))){
      pos=2*pos+1;
      // if (pos!=nextprime(int(p)).val) CERR << "error " << p << endl;
      return pos;
    }
  }
  return -1;
}

typedef unsigned long long ulonglong;

size_t GCrible(const vector<ulonglong> & premiers,ulonglong n,int fam){
  int cl=clock();
  size_t lencrible=n/30,nbpremiers=premiers.size();
  vector<bool> crible(lencrible,true);
  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!=fam)
      reste += pi2;
    reste /= 30;
    indices[ i]=reste;
  }
  ulonglong nslices=lencrible/3000000,currentslice=0;
  for (;currentslice<nslices;++currentslice){
    size_t slicelimit=currentslice+1;
    slicelimit=slicelimit==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 += int(crible[index]);
  cout << "Nombre premiers criblés famille " << fam << " entre "<< n << " et " << n2 <<": " << total << " time " << (clock()-cl)*1e-6<< endl;
  return total;
}

int main(int argc,char ** argv){
  vector<unsigned> crible;
  ulonglong N;
  int fam=1;
  if (argc>1){
    N=atoll(argv[1]);
    if (argc>2)
      fam=atoi(argv[2]);
  }
  else {
    cout << "Syntaxe " << argv[0] << " N fam. Donnez N puis fam: " ;
    cin >> N;
    cin >> fam;
  }
  double sqrt2N=unsigned(std::sqrt(2*double(N)));
  fill_crible(crible,sqrt2N);
  vector<ulonglong> premiers;
  for (ulonglong p=7;p<=sqrt2N;){
    premiers.push_back(p);
    p=nextprime(crible,p);
    if (p==unsigned(-1)) 
      break;
  }
  GCrible(premiers,N,fam);
}

LEG · December 2018

X:-((tu)

Mais comment et ou je copie et colle dans Cod::bloc que j'ai installé avec le compilateur Gcc

j'ai ouvert, j'ai jeté un oeil....pour moi c'est une nébuleuse....

Par contre ton programme il a l'air d'enfer....reste plus qu'a l'exécuter pour moi....
1) je dois le copier dans l'éditeur ..ok..mais c'est quoi...dans Cod bloc...?
2)puis ensuite compiler :-S::o
3) exécuter .....
4) comment tu rentres la valeur : ok vu

5) pour changer la famille je le fais dans le programme à la ldemande :

.....OK c'est vu

brian · December 2018

@LEG

Pour utiliser ce que j'ai écrit, le plus simple en fait est de le coller tout seul dans un fichier à part, mettons dans le fichier my_bit_array.py, situé dans le même répertoire que ton code (ou alors il faut qu'il puisse être trouvé via sys.path). Ensuite, en haut de ton fichier, après les imports existants, tu mets :

from my_bit_array import MyBitArray

Avec ça, tu n'as plus qu'à changer la ligne

crible = n//30*[1]

de ton code comme indiqué plus haut, en

crible = MyBitArray(n//30, init=1)

Avec cette méthode, il n'est pas nécessaire de toucher aux tabulations de ton code.

parisse a écrit:

@brian : on va gagner en mémoire, mais le code obtenu sera encore plus lent que le code Python originel qui est déjà environ 10 fois plus lent que le code C++ que j'ai donné (...). Utiliser un langage interprété pour faire un crible efficace ne me semble pas du tout une bonne idée.

C'est clair. Moi, j'ai juste écrit ça au cas où Python serait dans le cahier des charges (p. ex. pour des raisons éducatives) et pour montrer qu'on peut facilement régler sans changer de langage le problème d'occupation mémoire excessive de l'algo posté à l'origine. Mais si le seul critère est la performance, il est clair que C++ est plus indiqué.

LEG · December 2018

Ok @Brian
Mais justement mon But c'est la rapidité et la limite N comme l'a indiqué @ Parisse
je n'ai pas de cahier des charges...C'est personnel ..
le ^problème , je viens d'installer Codebloks avec son compilateur sur le lien qu'à indiqué Parisse.
j'ai ouvert Codblock et c'est le noir complet
pour y copier son fichier programme, le compiler, l'exécuter ...etc

parisse · December 2018

Alors, d'abord s'assurer qu'on a bien installe un compilateur.
Par exemple installer codeblocks sous windows (selectionner le setup codeblocks + mingw pour installation)
Puis File>New>Empty File
recopier le fichier goldbachs.cc
File>Save File as, par exemple test.cc, puis Build>Compile et Run
Attention, ne pas recopier le code ci-dessus, le forum a mange une partie du source, les indices i par exemple.

[Il faut mettre une ' ' entre [ et i sinon, l'afficheur du forum le prend pour une bannière BBcode de mise en italique et mange ce qui est entre [ ]. AD]

LEG · December 2018

c'est ce que je viens de faire avec ton programme C++:

résultat :

Donnez N puis fam: 300000000 1

Nombre premiers crible famille 1 entre 300000000 et 600000000: 1884105 time 0.
000562 ; soit 5 dixièmes de secondes

Press any key to continue.
*****************************************************************************************************
avec Python :

========= RESTART: E:\executable algo P(30)\Crible_G.T.Y_modulo30.py =========
Donnez N: 300000000
Nombre premiers criblés famille 1 entre 300000000 et 600000000: 1884105

1.24
--- Temps total: 1.27 sec

tu es sûr qui n'y a pas un problème...?

.............OK ,vu aussi impeccable,(tu) les temps sous linux ne correspondent pas mais il va plus vite que Python.

LEG · December 2018

je viens de réessayer avec n = 3000 000 000 il affiche un temps qui ne correspond pas environ 6 seconde et il affiche 19 secondes ???:-S

ok c'est vu il affiche un temps qui prend tout en compte, jusqu'au moment ou j'appuie sur une touche pour recommencer.

parisse · December 2018

Le temps affiche est correct sous linux, sous windows je n'en ai aucune idee. Le temps total affiche tient compte du temps de saisie de N et fam.

LEG · December 2018

Ok Parisse , en tous cas il va plus vite que sous python j'ai lancé 24 giga environ 45 secondes au lieu de 130...

Une petite question :
lorsque je clic sur l’icône de l'application la fenêtre cmd s'ouvre bien, il exécute mais dès qu'il a fini la fenêtre se ferme de suite, donc on ne voit pas le résultat peut-être faut-il un : system ("pause") en fin de programme comme pour python, et from os import system au début ... non ?

parisse · December 2018

La fenetre se ferme parce que windows n'est pas oriente ligne de commande. Sous Mac ou linux, on lance le programme depuis un terminal et la question ne se pose pas. Ici on peut ajouter un cin a la fin pour forcer une pause (par exemple cin>>N;)

Notez que vous pouvez ameliorer la vitesse depuis le menu Settings>Compiler puis dans Compiler settings, assez loin Optimization choisissez -O3
A noter aussi que la vitesse depend du compilateur. Si vous avez installe mingw sous windows, vous avez un executable 32 bits, qui va aller moins vite qu'un executable 64 bits.

LEG · December 2018

C'est fait pour setting 03
sur le site code::bloks il ne propose pas mingw sous Windows 64 bit... et en 32 bit il plante pour N = 150 Giga

Pour la fenêtre dos cela ne fait rien car je lance depuis la console Code::bloks ce qui ne me gène pas...
Il marche "lefeu" de dieu ... Un grand Merci

Si le programme t'intéresse et que tu veux le faire pour Eratosthène (mod30)c'est presque pareil: EcribleGP_mod30
la première partie ne change pas pour extraire les premiers P , mais on a besoin que de la limite:

def eratostene(n):
    n = int(n**0.5)

donc : $n\leqslant\sqrt{n}$

dans cette partie :

def ECribleGP_mod30(n):
    # INITIALISATION
    start_i= time()
    Primes_init = eratostene(n) # remplacer par P = eratostene(n)
    nbcell=n//30
    nombres=[]

on a pas besoin de nn = 2n

c'est dans cette partie ci-dessous que cela va changer, car effectivement on a pas besoin de calculer les restes:
R_i pour chaque Premier.
Et le calcul de l'index pour chaque Premier est "différent"; car on ne calcul pas l'index par rapport à j = R_i mais par rapport au produit de j = (pi*P), puis on calculera l'index de départ de P , pour cribler par pas de P; d'où j//30 = index
et pi est la base des 8Familles {1,7,11,13,17,19,23,29} permettant de calculer le produit J pour chaque premier P
Afin qu'ensuite on puisse déterminer j%30 = P8 et:
P8 ={1:0;7:1;11:2;13:3;17:4;19:5;23:6;29:7} l'ordre des 8 familles

voila ce que cela devrait donner:( '"attention je ne suis pas programmeur")

for i in range(1):
        nombres.append([1]*nbcell)
    Pfam,P8=[],{1:0}   # On a besoins de  pi = {1,7,11,13,17,19,23,29} pour calculer j = produit
    s_1=time()-start_i
    print("Phase d'initialisation: %s seconds ---" % s_1)

    # FAMILLES POUR CHAQUE Pi
    start_time = time()
    for i,pi in enumerate(Primes_init):
        Pfam.append([0])
        r=nn%pi      # Ca devient inutile...
        debut,fin,pas=r+pi*(1-r%2),min(pi*30,n),pi*2   # Ca inutile, mais début,fin = pi*P,....pi*p
        for j in range(debut,fin,pas)   :# Ca devient,  for j in range(debut,fin) :
            Pf=Pfam["i]   
            if j%30==1: # Attention j = produit de pi*P
                fam = P8[1]
                if Pf[fam] == 0:
                    Pf[fam] = j

        for j in range(1):
            debut_index=Pf[j]//30
            Nombres_j=nombres[j]
            for index in range(debut_index, nbcell,P): # Attention par pas de P et non pi
                Nombres_j[index] = 0
    s23=time()-start_time
    print("Famille de chaque Pi: : %s secondes ---" % s23)

la fin devrait pas changer....en principe..

 # CALCUL DES NOMRES PREMIERS ENTRE n ET 2*n
    start_time = time()
    total = 0
    for sous_liste in nombres:
        total+=sum(sous_liste)
    s_4=time() - start_time
    s=s_1+s23+s_4
    print("Extraction des premiers n à 2*n : %s seconds ---" % s_4)
    #print(nombres)
    return total,s_1+s23+s_4,

n = int(input("Donnez la valeur de n = 30k : "))
nbr,s= ECribleGP_mod30(n)
print ("\n** ",nbr,"nombres trouvés en %s secondes" % s ,"**")
system("pause")

Moi je n'ai pas essayé, car je ne suis pas sûr de bien le faire avec python...encore moins avec C++

J'espère du coup, que @Rescassol n'est pas parti au Restau du cœur ... :)o car on ne l'entend plus ... ;-) et je serais bien allé au jardin des sens ...

À Grenoble il y a un bon restau ... à Annecy il y a le chef au grand chapeau noir ...

Passe une bonne soirée ...
LEG

parisse · December 2018

Ah oui, je ne pensais pas du tout a cette histoire de restau, je voulais verifier que mon hypothese sur la memoire etait bien la bonne et aussi montrer ce qu'on pouvait gagner avec de l'experience en C++ par rapport a du Python, qui est beaucoup trop a la mode a mon gout. Que ca ne vous empeche pas de prendre un repas avec Rescassol a ma sante!

LEG · December 2018

Salut @Parisse
envoie moi par mail si un restau te plait à Grenoble...je pense que @Rescassol me chambrer ...(:P)

Pour la suite il est clair que ton programme fonctionne beaucoup mieux que celui en Python GcribleGTY et de plus j'étais limité à 29 700 000 000 où il mettait 400 secondes...

là ma limite se situe entre 120Go et 150Go ..en 32bit donc si toi tu as fait le teste sous Linux en 64bit , avec des performance très honorable pour le crible de Goldbach de N à 2N.
En installant l'application 64 bit pour windows dans code:bloc , on passe à une limite N = 7*10¹² en moins d'un heure...

Donc cela serra encore plus performant avec Eratosthène mod30, qui crible jusqu'à N...
l'éxécutable que je t'ai envoyé avec un ancien programme C++, où l'algorithme n'est pas optimisé, car il n'a pas respecté par exemple la limite du conjoint $P\leqslant\sqrt N$ extrait par les 8 bases p_i, et d'autre détails...me donne la limite N = 450Go, soi N /30 = 15Go de 1 par famille à cribler en un peu plus de2 heurres...loin de ta perf...

mais on peut le faire et le modifier avec la même méthode de Goldbach , ce que je viens d'expliquer ci-dessus ...il n'y a pas grand chose à faire...

A+
Leg

LEG · December 2018

pour modifier Goldbachmod30 en Eratosthènemod30, suivant le même programme et principe..

j'ai voulu modifier la partie du programme ci-dessous relatif au programme GCrible posté il y a deux jours..

def GCrible(premiers, n, fam):
    start_crible = time()
	
    # On génère un tableau de N/30 cases rempli de 1
    crible = n//30*[1]
    lencrible = len(crible)

    # On calcule les restes: ri = 2*n/pi
    nbpremiers = len(premiers)
    n2 = 2*n
	
    for i, premier in enumerate(premiers):
        reste = n2 % premier
	# tant que ri % 30 != fam on fait ri += 2pi
        if reste % 2 == 0:
            reste += premier
        pi2 = 2*premier
        while reste % 30 != fam:
            reste += pi2
        # Ensuite on divise ri par 30 pour obtenir l'indexe
        reste //= 30
        # On crible directement avec l'index
        for index in range(reste, lencrible, premier):
            crible[index] = 0

par cette partie afin de cribler jusqu'à n/30 où on remplace la fonction reste par une fonction multiplicative j qui est le produit de pi*premiers, où: pi est une des 8 valeurs {1,7,11,13,17,19,23,29} ensuite on calcul l'index de j et on crible par pas de premiers comme le GCrible qui devient ECrible.
je met un # aux lignes modifiées

on modifiera la première ligne de: def eratostenne
n = int(n**0.5) #sqrt de n et non de 2n

def GCrible(premiers, n, fam):
    start_crible = time()
	
    # On génère un tableau de N/30 cases rempli de 1
    crible = n//30*[1]
    lencrible = len(crible)

    # On calcule les produits j  ###
    nbpremiers = len(premiers)
    [color=#FF0000]pi = {7,11,13,17,19,23,29,31}  # les 8 valeurs de pi pour calculer les 8 j au maximum
    J = pi * premiers ## au lieu de:  reste = n2 % premiers
   
 
    # tant que j % 30 != fam on fait pi*premiers   
    for i, premier and pi in enumerate(premiers):
       j = pi*premier [/color]
       while j % 30 != fam:  ### on calcul j = pi *premiers et non le reste
            
	[color=#3300FF]# c'est cette partie en rouge ci-dessus de la fonction multiplicative, qui ne fonctionne pas pour ensuite cribler..[/color]
       
        # Ensuite on divise j par 30 pour obtenir l'indexe   ## modifiée ##
       j //= 30

        # On crible directement avec l'index
        for index in range(j, lencrible, premier):
            crible[index] = 0

Et ça plante erreur :

=== RESTART: E:\Documents\Conjecture de Goldbach\Crible_G.T.Y_modulo30.py ===
Donnez N: 3000
Traceback (most recent call last):
File "E:\Documents\Conjecture de Goldbach\Crible_G.T.Y_modulo30.py", line 83, in <module>
main()
File "E:\Documents\Conjecture de Goldbach\Crible_G.T.Y_modulo30.py", line 78, in main
ECrible(premiers, n, 1)
File "E:\Documents\Conjecture de Goldbach\Crible_G.T.Y_modulo30.py", line 52, in ECrible
j = pi * premiers
TypeError: can't multiply sequence by non-int of type 'set'
>>>

exemple :

n = 3000 on a initialiser les 1 , 3000 /30 = 100, soit 100 cellules de 1
je prends premiers = 7
je calcule J = pi *7……….donc 8 produits au maximum, en vérifiant si j %30 == 1 car on crible la fam 1.

[7*7, 7*11, 7*13 == 1%30 ]; donc ok et je n’ai pas besoin d’aller jusqu’à pi = 29 pour calculer 7*29, d’accord….

Puis je vais calculer son index j = 91 , 91//30 = 3
Que Je positionne cellule 3 et je crible par pas de premiers = 7…de 3 à n//30 on remplace les [1] par [0] tous les 7 pas….etc… on réitère avec premiers = 11…..premiers <= sqrt de n et non de 2n, car c’est Eratosthène….modulo 30

[11*7,11*11 == 1%30 ]; ok
calcul de l'index :
j //30 = 4
que l'on positionne cellule 4, crible par pas de 11 de 4 à n//30 ...etc on réitère avec premier = 13....

13*7 == 1%30 ok, position index = 3, crible par pas de 13 de 3....>n//30 ...on réitère premier = 17 ...

[17*7, 17*11, 17*13, 17*17, 17*19, 17*23 == 1%30 ]; ok positionne cellule 13, crible par pas de 17de 13....>n//30 ...etc

Rescassol · December 2018

Bonjour,

Oui, je plaisantais, le Jardin des Sens à Montpellier coûte la peau des fesses.

Cordialement,

Rescassol

LEG · December 2018

@Rescassol
oui , mais pas plus que le Toqué à Montréal... Tu peux te racheter en modifiant la partie

 for i, premier in enumerate(premiers):
        reste = n2 % premier
	# tant que ri % 30 != fam on fait ri += 2pi
        if reste % 2 == 0:
            reste += premier
        pi2 = 2*premier
        while reste % 30 != fam:
            reste += pi2
        # Ensuite on divise ri par 30 pour obtenir l'indexe
        reste //= 30
        # On crible directement avec l'index
        for index in range(reste, lencrible, premier):
            crible[index] = 0

remplacer le reste de 2n% premier et son incrémentation, par:
le produit de la liste des variables vp a= 7,b=11,c=13,d=17,e=19,f=23,g=29,h=31 ; vp* premiers ;

tant que produit % 30 != fam , en fonction de fam choisie {1,ou 7....ou 29}

ensuite on calcul l'index du produit...et on crible

puis on réitère pour chaque premiers énuméré par la fonction...

Je sens que notre "Cher Ami" Parisse B, va choisir le restau de Marc Veyrat à Annecy....:)oX:-(

LEG · December 2018

Bonjour
@Rescassol et amis de l'algorithme de Goldbach.

Suivant le post ci-dessus afin de modifier le crible de Goldbach en Eratosthène modulo 30, je pense qu'il y a plus simple et qui optimiserait l'algorithme /crible.
Explication dans le document joint, suite au 2 posts ci-dessus .
modifié le 10/03/2019

Cordialement à tous
LEG

LEG · January 2020

Bonjour
j'aurais une petite question sur le fait de slicer dans un programme C++

Ce que Mr Parisse B a fait dans le programme ci-dessus.

Si vous avez besoin de plus de vitesse encore, je pense qu'il faut slicer,

Est-ce que cette fonction agit aussi sur la mémoire Ram ? Dans qu'elle limite faut-il $slicer$ je n'ai trouvé aucune réponse... Merci d'avance d'une réponse.

Par exemple si on remplace la valeur dans la ligne de programme ci-dessous :

nslices=lencrible/3000000

Exemple : par 1500000 ? Pour l'instant je n'ai pas touché ...ok c'est vu on accélère si on trouve la bonne tranche....

Actuellement la limite arrive péniblement entre $7*10^{12}$ et $7,5*10^{12}$ pour un temps 2182 secondes

Mon Pc : 8Go de ram installé ; 64bits ; CPU; 3,60 GHz

    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==fam){
	produit /= 30;
	break;
      }
    }
    indices[ i]=produit;
  }
  ulonglong nslices=lencrible/3000000,currentslice=0;
  if (nslices==0) nslices=1;
  for (;currentslice<nslices;++currentslice){
    size_t slicelimit=currentslice+1;
    slicelimit=slicelimit==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;

Cordialement.

Demande conseil pour python

Réponses

Bonjour!

Catégories

In this Discussion

Qui est en ligne 37