ton dernier post de 16h38 : effectivement je n'avais pas compris que tu parlais du
h d'Eratost
hène
est ce que ça veut dire que dans mes deux programme "Pycharme " il faut que je mette le
h dans tous les Eratost
hène, où il ne figure pas...et ensuite ...?
que dois faire le programme :
on rentre la valeur n,
on fait appel à eratosthène pour cribler de 1 à
\(\sqrt{2n}\) pour obtenir les premiers
\(P_i\leqslant\sqrt{2n}\) qui vont être utilisé par le crible_G à partir de la:
def crible_G(n):
nombres = n*[1]
nombres[0] = 0
p = eratostene(math.sqrt(2*n))
lenp = len(p)
r = []
for i in range(lenp):
..etc..
le programme fait la liste des entiers naturels de 1 à n , représenté par des 1
exemple n = 1000:
11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111 .......jusqu'à n
donc chaque 1 est un entier 1,2,3........n.
eratosthène à extrait les premiers
\(P_i\leqslant\sqrt{2n}\) donc < à 44.
soit la liste des $P_i$ :
{2.3.5.7.11.13.17.19.23.29.31.37.41.et 43}
le crible_g va utiliser ces $P_i$ : pour calculer le reste
R de 2000 par chaque $P_i$ .
Soit les
R =
{0.2.0.5.9.11.11.5.22.28.16.2.32 et 22}
le crible _g va donc cribler les entiers représentés par 1, $\equiv{2n} [P_i]$ selon le même principe qu'Ératosthène , mais en partant du reste R de 2n Par Pi. On marquera donc tous les entiers non nul de 1 à n, qui sont égaux modulo Pi avec 2n , c'est à dire qui partagent le même reste R modulo Pi
("si il n'y a pas R = 1, alors 2n -1 est premier, donc le premier 1 ne peut être remplacé par 0 et de la même façon si
R = 0 on part directement de $P_i$")
sinon on part de
R.
le premier couple
R + P_i est : (
0 ; 2) on part donc du deuxième entier = $P_i = 2$ que l'on marque 0, puis tous les 2 nombres...
10101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101......jusqu'à n
le deuxième couple
R + P_i est : (
2 ; 3) on marque donc le deuxième entier d'un 0, puis tous les 3 nombres...
101000101000101000101000101000101000101000101000101000101000101000101000101000101000101000101000101000101000101000101000101000101000101000101000101000101000101000101000......jusqu'à n
le troisième couple
R + P_i est : (0 ; 5) on part donc du cinquième entier =$ P_i = 5$ que l'on marque 0, puis tous les 5 nombres
1010001010001000001010000100000100010100010100010000010100001000001000101000101000100000101000001000101000101000100000101000001000101000101000100000101000001000101000......jusqu'à n
le quatrième couple
R + P_i est : (
5;7) on part donc du cinquième entier que l'on marque 0, puis tous les 7 nombres
1010001010001000000010000000000100010100010100010000000100000000001000101000101000100000001000001000100000101000100000101000001000101000001000100000100000001000101000......jusqu'à n
le cinqième couple
R + P_i est : (
9;11) on marque donc le neuvième entier d'un 0, puis tous les 11 nombres
1010001000001000000010000000000100010100000100010000000100000000001000101000101000100000001000000000100000101000100000001000001000101000001000100000100000001000101000......jusqu'à n
....etc...
A la fin on compte les 1 les entiers qui ne sont congrus à 2n mod P_i, donc: qui donnent les nombres premiers q entre 1000 et 2000
puisque si un entier A de 1 à n est non congrus à 2n[Pi], il ne partage pas le même reste R avec 2n, par conséquent Pi ne divise pas cette différence tel que 2n - A, alors 2n - A est un nombre premier q . Tout entier < 2n, non divisible par un nombre premier Pi < racine de 2n, est un nombre premier : selon Ératosthène.
C'est tout simplement le crible d'eratosthène mais dans les congruences , au lieu de partir de P_i pour barrer leurs multiples, on part de R et on barre tous les congruents de P_i....Voila....