Trouver facilement petits nombres premiers
Salut.
Comme d'habitude je viens faire part de mes petites trouvailles.
Un algorithme pour trouver facilement des petits nombres premier hormis des carré de 5 et de 13 qui de sont faufilé par la et peut être un carré de 7, etc...
Ça commence a dégénérer a partir de 209, j'ai pas pris le temps de réfléchir a tout ça.
On verra demain.
$1\pm1= 0 : 2$
__________________________________________
$1\times2\pm1= 1 : 3$
__________________________________________
$1\times2\times3\pm1= 5 : 7$
$1\times2\times3\pm5= 1 : 11$
$1\times2\times3\pm7= -1 : 13$
$1\times2\times3\pm11= -5 : 17$
$1\times2\times3\pm13= -7 : 19$
$1\times2\times3\pm17= -11 : 23$
$1\times2\times3\pm19= -13 : 25$
$1\times2\times3\pm23= -17 : 29$je m'arrête a 29 inf a $30=1\times2\times3\times5$
________________________________________________
$1\times2\times3\times5\pm1= 29 : 31$
$1\times2\times3\times5\pm29= 1 : 59$
$1\times2\times3\times5\pm31= -1 : 61$
$1\times2\times3\times5\pm59= -29 : 89$
$1\times2\times3\times5\pm61= -31 : 91$
$1\times2\times3\times5\pm89= -59 : 119$
.......
$1\times2\times3\times5\pm169= -139 : 199$
je m'arrête a 199 inf a $210=1\times2\times3\times5\times7$
________________________________________________________
$1\times2\times3\times5\times7\pm1= 209 : 211$
Comme d'habitude je viens faire part de mes petites trouvailles.
Un algorithme pour trouver facilement des petits nombres premier hormis des carré de 5 et de 13 qui de sont faufilé par la et peut être un carré de 7, etc...
Ça commence a dégénérer a partir de 209, j'ai pas pris le temps de réfléchir a tout ça.
On verra demain.
$1\pm1= 0 : 2$
__________________________________________
$1\times2\pm1= 1 : 3$
__________________________________________
$1\times2\times3\pm1= 5 : 7$
$1\times2\times3\pm5= 1 : 11$
$1\times2\times3\pm7= -1 : 13$
$1\times2\times3\pm11= -5 : 17$
$1\times2\times3\pm13= -7 : 19$
$1\times2\times3\pm17= -11 : 23$
$1\times2\times3\pm19= -13 : 25$
$1\times2\times3\pm23= -17 : 29$je m'arrête a 29 inf a $30=1\times2\times3\times5$
________________________________________________
$1\times2\times3\times5\pm1= 29 : 31$
$1\times2\times3\times5\pm29= 1 : 59$
$1\times2\times3\times5\pm31= -1 : 61$
$1\times2\times3\times5\pm59= -29 : 89$
$1\times2\times3\times5\pm61= -31 : 91$
$1\times2\times3\times5\pm89= -59 : 119$
.......
$1\times2\times3\times5\pm169= -139 : 199$
je m'arrête a 199 inf a $210=1\times2\times3\times5\times7$
________________________________________________________
$1\times2\times3\times5\times7\pm1= 209 : 211$
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
simplification de l'algorithme.
$1\pm1= 0 : 2$
__________________________________________
$1\times2\pm1= 1 : 3$
__________________________________________
$1\times2\times3\pm1= 5 : 7$
$1\times2\times3+5= 11$
$1\times2\times3+7= 13$
$1\times2\times3+11= 17$
$1\times2\times3+13= 19$
$1\times2\times3+17= 23$
$1\times2\times3+19= 25$
$1\times2\times3+23= 29$je m'arrête a 29 inf a $30=1\times2\times3\times5$
________________________________________________
$1\times2\times3\times5\pm1= 29 : 31$
$1\times2\times3\times5+29= 59$
$1\times2\times3\times5+31= 61$
$1\times2\times3\times5+59= 89$
$1\times2\times3\times5+61= 91$
$1\times2\times3\times5+89= 119$
.......
$1\times2\times3\times5+169= 199$
je m'arrête a 199 inf a $210=1\times2\times3\times5\times7$
________________________________________________________
$1\times2\times3\times5\times7\pm1= 209 : 211$ ???????
Tu fais abc + ... un nombre qui est premier avec a , b et c , mais tu t'arrêtes juste avant d². Et tu as l'assurance d'avoir uniquement des nombres premiers.
Idem abdc + un nombre qui est premier avec a,b,c et d en s'arrêtant juste avant e² , idem, tu n'as que des nombres premiers.
Etc
Problème, dès 2x3x5x7, on est déjà au delà de 11². Et donc, tu ne génères aucun nombre.
1) Ton algorithme n'est pas complet tu as oublié (2*3*5) = 30 et 30 + 7 ...etc
Tu fais simplement les 8 familles : $Fam(i) + 30k$ avec $i\in (1,7,11,13,17,19,23,29)$
si tu veux que des nombres premiers d'une des 8 Fam(i) tu construis l'algorithme
en te servant de ces 8 nombres ; mais attention tu remplaces 1 par $31$ car 1 n'est pas premier , donc il ne servirait pas dans l'algorithme:
Exemple pour la $Fam (7)$ ; $30k +7$ :
tu as les 4 couples ou produits de $i$ ; $(7*31)$ ; $(11*17)$ ; $(13*19)$ et $(23*29)$ qui te permettent d'extraire les nombres premiers de la $Fam (7)$
il y a plusieurs méthode pour construire l'algorithme et le programme....
Par exemple avec cette méthode :
Tu écris la suite arithmétique 7 de raison 30 et tu pars du produit de ces couples $i$....en marquant par $pas$ de $i$ jusqu'à la limite $n$ fixée.
$7; 37; 67; 97; 127; 157; (187); (217); (247); 277; 307;......(667).... n = 30k+7$
Puis tu réitères : tu refais les couples en utilisant les mêmes Fam(i) augmentées de 30 avec $i'\:premier\leqslant\sqrt{n}$ en gardant les $8(i)$ de base pour construire les couples ou produits .
$(7*61)$ ; $(31*37)$ ; $(11*47)$ ; $(17*41)$ ; $(13*79)$ ; $(43*19)$ et $(23*59)$ et $(29*53)$
$(67*31)$ ; ; ; $(17*71)$ ; $(13*79)$ ; $(19*73)$
Tu l'auras compris seul les $i' > 31$ partent et marquent par pas de $i'$ ....jusqu'à la limite $n = 79^2$ pour cet exemple , qui est le dernier premier $P\leqslant\sqrt{n}$ $= 6247$
soit : $6247//30 = 208$ entiers à cribler dans cette $Fam(7)$
pour la même limite et les autres Fam(i) tu changes les 8 couples de base $(i)$ pour obtenir $30k + i$
Bon amusement....
Je cherchais :
Tu fais simplement les 8 familles :$Fam(i) + 30k$ avec $i\in (1,7,11,13,17,19,23,29)$
Je vais prendre le temps de comprendre les autres algorithmes. OK lourran
Oui il te suffit:
tu fixes la limite $n$ 30k
tu fixes la famille $Fam(i)\in(1,7,11,13,17,19,23,29)$ par exemple $Fam\; 11$
0) tu fais le tableau du nombre de cellules = $n // 30$
1) tu vas utiliser uniquement les nombres premiers $A = [7,11,13,17,19,23,29,31]$
2) puis il te faut les nombres premiers $B\leqslant\sqrt{n}$ extrait par un petit programme d'Ératosthène en début de programme ou dans une liste que tu appelles ensuite.
puis on calcule l'index de départ $idx = j // 30$
cet index est la position de départ , de l'indice du produit
les indices sont numérotés de 0 à n//30 : 0,1,2,3,..... ce qui correspond au n° du nombre dans sa cellule pour la fam fixée.
exemple Fam 11 :
$11,41,71,101,......n//30.$
$j = a*B =7*23$
j%30 = 11
$idx = 161//30 = 5$ # ce qui va te donner le rang 5, donc le 6ème nombre, qui correspond bien à : $5*30 + 11 = 161$
à partir de ce rang que tu marques 0 et tous les 7 pas, tu marques 0 = multiple de 7 ....jusqu'à .....$n//30$
puis idem avec 23 , par pas de 23 tu marques 0 = multiples de 23 ....jusqu'à .....$n//30$.
ensuite tu réitères avec les autres couples $13*17$ ; $11*31$ ; 19*29 ...etc....
puis 7 * (B+30k) ; 11*(B+30k) ; 13 * (B+30k) ; 17 * (B+30k) ; 19*(B+30k) ; 23*(B+30k) ; 29*(B+30k)
où : $B+30k$ sont bien les nombres premiers extrait au début par Ératosthène et rappelés par le programme.
à la fin, tu fais la somme des nombres premiers qui ne sont pas marqués 0.
tu constateras que tu cribles jusqu'à $n$ , modulo (B*30)
pour info sur mon Pc en C++ limite 7 500 000 000 000 et je double la limite avec une variante utilisant les congruences , c'est à dire :
on part du reste $R$ de la division de $2n$ par $P\leqslant\sqrt{2n}$; "" mais en criblant toujours la même limite n avec la même Fam(i) ""
Bon bref en gros.
a*b+c*d = à ce que tu veux sauf a,b,c,d parque tu ne peux pas écrire
a*b+c*d =a*(...) ou a*b+c*d =b*(....) ou c*(...)
Maintenant tu prends une primorielle et un nombre x premier avec par exemple
2*3*5*7*11*13-x=a
et si a est plus petit que 17^2 alors a et premier parce que tu ne peux pas mettre en facteur 2,3,5,...13 dans a et juste pour le fun remplace x par un nombre premier jumeaux et à l'arrivée a le sera aussi.
En gros dans ton exemple 1 n'a aucun facteur commun avec ta primorielle et a est plus petit que ...
et donc cela donne un premier.
cdl Cordialement [? AD]
remy.