Bonjour
je voudrais modifier uniquement la taille du tableau à cribler $(n//30)$...sans modifier le reste uniquement le nombre de cellules marquées $1$ , inférieur à $n$ diviser par 30, réduire cette taille du tableau à la racine carrée de $n$ : exemple $n = 3000 // 30$ donne 100 cellules à cribler , et racine de $3000 // 30 = 54$ cellules à cribler., de sorte que pour une valeur $n = 10^{10} = 10 000 000 000$ je n'aurait que $\sqrt{10^{10}} = 100 000$ cellules à cribler.
je n'ai pas trouver quel paramètre modifier dans la ligne ou les lignes du programme posté ci-dessous # (ok , j'ai trouvé)
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) ##(si on fusionne les deux cribles il faudra rentrer, int((2n)**0.5) pour Goldbach.
prime_E =[2]
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]:
prime_E.append(each_number)
for multiple in range(each_number*each_number, n+1, each_number):
sieve_list[multiple] = False
#print(prime_E[2:])
return prime_E[2:]
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
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
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 = eratostene(n)
start_time = time()
## On crible
fam=19 ## 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")
En exemple pour la valeur limite de $n = 3000$ , soit 100 + 1 cellules à cribler :
résultat : crible Ératosthène : [1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 0, 1, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 1, 1, 1, 0, 0, 1, 0, 1, 0, 0, 0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 0, 1, 1]
Nombre premiers criblés famille 1 : 8 ----- 0.0
crible É ET G: [0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1]
Nombres P' non congru 2n[pi] ou couple P'+q = 2N, de (i) à 3000 famille 1 : 20 ----- 0.0
et pour (racine de 3000) //30 = 1,8... cellule à criblée pour de petites valeurs , c'est inutile bien sûr...
je pense que c'est dans cette partie qu'il faut rentrer la racine de (n //30 +1) ,
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
lencrible = ((n1//30)+1)
j'ai modifié .... ça marche , ...
c'est pour cribler de grande valeur $> 10^{10}$ afin de réduire le temps et la mémoire prise par le tableau . Il est clair que le resta du programme ne changera pas , car il nous faut toujours les nombre premiers $P\leqslant\sqrt{n}\;ou\;2n$ pour cribler...