Informatique et crible d’Atkin .

Les meilleures performances après Erathostene sont celles d'Atkin.
Mais là adhoc je suis très perplexe.
Je ne sais pas trop quoi en penser.

Screenshot_20240111-183521.jpg

Screenshot_20240111-184515_Gallery.jpg

Voici un source Atkin:
#include stdio.h
#include stdlib.h
#include conio.h
#include math.h
#include time.h
#include new

int main ( )
{
int comptageNP =0;
int limite ;
int wlimit ;
int z ;
printf ( "Programme Atkin . \nVeuillez insérer un nombre limite en dessous duquel tous les nbres premiers seront calculés : " ) ;
scanf ( "%d" , & limite ) ;
time_t debut = time(NULL);
bool * sieb = new bool [limite];
wlimit = sqrt ( limite ) ;

for ( int x = 1 ; x <= wlimit ; x++)
{
for ( int y = 1 ; y <= wlimit ; y++ )
{
z = 4 * x * x + y * y ;
if ( z <= limite && ( z % 60 == 1 || z % 60 == 13 || z % 60 == 17 || z
% 60 == 29 || z % 60 == 37 || z % 60 == 41 || z % 60 == 49
|| z % 60 == 53 ) )
{
sieb [ z ] = ! sieb [ z ] ;
}
z = 3 * x * x + y * y ;
if ( z <= limite && ( z % 60 == 7 || z % 60 == 19 || z % 60 == 31 || z
% 60 == 43 ) )
{
sieb [ z ] = ! sieb [ z ] ;
}
z = 3 * x * x - y * y ;
if ( x > y && z <= limite && ( z % 60 == 11 || z % 60 == 23 || z % 60
== 47 || z % 60 == 59 ) )
{
sieb [ z ] = ! sieb [ z ] ;
}
}
}

for ( int je = 5 ; je <= wlimit ; je++ )
{
if ( sieb [ je ] == 1 )
{
for (int j = 1 ; j * je * je <= limite ;j++ )
{
sieb [ j * je * je ] = 0 ;
}
}
}

for ( int je = 5 ; je <= limite ;je++ )
{
if ( sieb [ je ] == 1 )
{
comptageNP++;
}
}
time_t fin = time(NULL);
printf ("\nTemps de recherche : %d secondes %d nombres premiers trouvés sur une recherche de 5 à %d", fin- debut,comptageNP,limite);
}

Screenshot_20240112-151024.jpg

Screenshot_20240112-151431.jpg

4 fois plus vite que Atkin avec la même bécane -->>>une simple tablette Android 🤣🤣🤣🤣🤣🤣
J’ai gagné quoi adhoc!!!!
Comme je garde mes sources je vais essayer de faire un exécutable cet AM sur le pc portable de belle maman.
Ciao mon grand.

https://fr.m.wikipedia.org/wiki/Crible_d%27Atkin

adhoc

12/01/2024 à 16h19

Genial. On va voir avec l'exe si le reatio est le meme. Good job!!!!

#include stdio.h
#include stdlib.h
#include time.h
#include math.h
#include sys/param.h
#include new

int main()
{

long int val,comptageNP=0,a;
int X,Y,test,affiche=0;
printf ( "Programme Personnel . \nVeuillez insérer un nombre limite en dessous duquel tous les nbres premiers seront calculés : " ) ;
scanf("%lu", &val);
printf(" Affichage Oui = 1 Non = 0 : ");
scanf(" %d", &affiche);
bool * Tableau2 = new bool [val];
time_t debut = time(NULL);
X = val - (val % 6);
Y=sqrt(X);

//TABLE MULTIPLICATIVE

for (long int i = 5 ; i <= Y; i = i + 2 )
{
if ( i % 3 == 0)
i = i+2 ;
for(unsigned long int j=i ; i*j < X; j = j + 2)
{
if ( j % 3 == 0)
j = j+2 ;
if ( i * j < X )
Tableau2[ i*j ]=1;
}
}
printf ("\n");

time_t fin = time(NULL);
printf ("\nTemps de recherche : %d secondes ", fin- debut);

//AFFICHAGE ET COMPTAGE

for ( unsigned long int i = 5 , j = 7 ; i <= X ; i = i + 6 , j = j + 6 )
{

if (Tableau2[ i ] ==0)
{
comptageNP++;
if (affiche == 1)
{
printf("\n i = %lu", i);
}
}
if (Tableau2[ j ] ==0)
{
comptageNP++;
if (affiche == 1)
{
printf("\n j = %lu\t", j);
}
}
}

printf ("\n %d nombres premiers trouvés sur une recherche de 5 à \n%d",comptageNP,val);

//TEST DE PRIMALITÉ
boucle :
printf("\n\n\n tester la primalité d’un nombre ou entrez 0 pour sortir : ");
scanf("%d", &test);
system("cls");
if (test == 0)
{
return 0;
}
else if ( test == 2 || test ==3 )
{
printf("\n le nombre à%d est premier",test);
goto boucle;
}
else if (test % 2 ==0 || test % 3 ==0 || Tableau2[test]==1)
{
printf("\n le nombre %d est composé",test);
goto boucle;
}
else
{
printf (" le nombre %d est premier",test);
goto boucle;
}
}

Désolé, c’est trop casse couille pour faire un exe avec les usines à gaz sous Windows. C’est devenu vraiment n’importe quoi aujourd'hui.
Tu as le source au moins. Il est très simple et c’est peut-etre pour ça qu’il pédale vite. J’ai 2 variantes pour remplacer le reste de la division entière des compteurs de boucle i et j car soi disant l’opérateur modulo 3 ( i%3) ralenti bcp le programme !!! En fait c’est tout le contraire.
Ciao!

adhoc

13/01/2024 à 09h08

Le modulo est un script interne ecrit en assembleur depuis quelques années. tres rentable. Il ya plus de 10 ans ca ramait beaucoup en effet. Ton programme en est la superbe illustration.

adhoc écrivait:
-----
> Le modulo est un script interne ecrit en assembleur depuis quelques années. tres
> rentable. Il ya plus de 10 ans ca ramait beaucoup en effet. Ton programme en est
> la superbe illustration.

Ben tu vois je savais pas. Merci pour l’info.
Je vais voir aujourd'hui pour réduire l’espace de stockage du Tableau2 de Booléens avec une gestion de la mémoire réduite sur les bits. Je bloque pour l’instant à 900 millions.

Screenshot_20240113-071045.jpg

adhoc

13/01/2024 à 10h42

Si tu es en 32 bits, tu as une limite vers les 4 milliards et du poil :-). 900 M semble etre une drole de valeur pour que ca bloque ou alors il ya d'autres valeurs parasites redondantes dans ton tableaun . Reverifie bien la declaration de ton tableau (int....)<. Ou alors sur un systeme 64 bits :-)

Déjà je suis convaincu d’être en 32 bits minimum.
Mais je ne peux travailler que sur 500 megaoctets de mémoire vive.
D’autre part le tableau déclaré est un tableau de Booléens et donc c’est le minimum du minimum pour stocker l’information 0 ou 1.
Ensuite l’allocation mémoire est dynamique avec le new, donc je réserve pas plus de mémoire qu’il m’en faut à priori.
Puis les boucles de calcul ne me donnent aucune redondance tel que par exemple 7×5 et 5×7 ( on essaye de les minimiser mais il y en aura tjs ex (11×11)×5 = 11×(11×5) soit 121×5 et 11× 55 etc etc.)
Voir copie d’écran ci jointe sur qq valeurs.
Sincèrement je ne vois qu’un manque de mémoire vive.
Merci encore.
Je vais voir si il existe d’autres failles.

Screenshot_20240113-115939.jpg

Screenshot_20240113-115844_Device care.jpg

adhoc

13/01/2024 à 12h17

Le tableau est de type booleen, mais quelle est sa longueur? C'est peut etre cela qu'il faudrait revoir.

adhoc écrivait:
-----
> Le tableau est de type booleen, mais quelle est sa longueur? C'est peut etre
> cela qu'il faudrait revoir.

Voilà mon pote!
1 octet d’espace mémoire.
Tu multiplies par 100000001.
Au moins je sais que je suis en 32 bits!!!!!
T’as beau chercher sur cette put' tablette samsung tu trouves Nada!!!!

Screenshot_20240113-140630.jpg

Screenshot_20240113-140606.jpg

Screenshot_20240113-141007_Chrome.jpg

Dans tous les cas ce compilateur sous android n’est vrt pas mal du tout. Il n’est pas au top pour déboguer et ne permet pas de faire des .exe ou équivalent sous android. Un plus.....on peut écrire en C et C++.
Tout le reste sous Windows n’est que de la merde pour celui qui veut apprendre car on perd trop de temps à chercher ce que B Gates a bien voulu imaginer avec son esprit tordu.
Peut-être il faudra que je passe à la version payante mais même 10 euros je ne les mettrai pas. Je me suis tjs démerdé seul au cabinet et j’estime avoir laissé trop de pognon dans tout le hard et software et avec le recul je m’aperçois que j’avais raison.
J’ai acheté à l’époque une version payante de c++ builder de Borland qui était buggé à mort ( mais on l’a appris que bcp trop tard).
Pendant des années j’ai fait avec le bloc-note de Windows et cela me suffisait pour classer mes fichiers patient et j’ai ainsi évité l’utilisation fastidieuse d’un classeur de bureau pour ranger les dossiers. C’est tout le bien que j’en ai retiré.
Bye bye.

Ici en lien une aide au C qui est vraiment ce qu’on peut trouver de mieux à mon avis. Suffit d’acheter les cartouches d’encre à un prix exorbitant 🤣🤣🤣.
https://zestedesavoir.com/tutoriels/755/le-langage-c-1/

Tiens adhoc un compilateur en ligne qui tient un peu la route.
Il marche dans les 2 sens d’un mobile sous Android vers un pc Windows et vice versa.

https://www.online-cpp.com/yFK67nagYM

adhoc

14/01/2024 à 22h32

Pour comprendre un peu d'ou vient ta limite, non sans mal, j-ai passé le programme en php pour pouvoir l'executer a partir d'un navigateur.
J'ai repris, toujours non sans mal, exactement TOUS tes algorithmes.
L'URL est:
https://animatedgif.biz/griffix

Ca fonctionne tres bien, sauf le timer que je dois corriger
Il bloque a 2M (un peu moins, toi, c'est 100M)L Le message d'erreur est
Fatal error: Allowed memory size of 134217728 bytes exhausted (tried to allocate 134217736 bytes) in /var/www/html/griffix/index.php on line 30

Soit la ligne de code:
$tableau2 = array_fill(0, $val, false);

EXACTEMENT ce que tu as dit.

Pour moi, en PHP, langage serveur internet que je maitrise mieux que C, je pense que la la limitation est dans mon fichier de configuration php.ini
memory_limit = 128M . C'est la limite memoire occupée par un script..Je peux modifier, a mes risques et perils !!! Un caractere de tableau occupe 1B. (1 octet).

Tu dois avoir dans tes reglage s de compilateur la meme chose, une memory limit, pour toi, plus importante, qu'il faut agrandir. Bonne recherche.



"

Je vais voir adhoc.
En attendant je pense diminuer la mémoire de stockage des np.
Peut être en stockant sur moins d’un octet au niveau des bits.
Voir cet article:
http://compoasso.free.fr/primelistweb/page/prime/eratosthene.php#:~:
text=Le%20crible%20d%27Eratosth%C3%A8ne%20es
t,non%20premier%20est%20dit%20composite

En C c’est possible.
J’ai fait tourner ton programme en Php. Tu vois c’est simple ce programme.🤣🤣🤣
Je sais aussi programmer en php. Le seul pb avec mon matos c’est de faire tourner ce langage sur un serveur local. J’ai pas de pc.
(La limite max de la tablette avant plantage est une recherche jusqu’à
900 Millions)

adhoc

14/01/2024 à 23h25

>Tu vois c’est simple ce programme.<

Pas trop de lignes mais la facon de raisonner est immense. Bravo. Continue a peaufiner, chef, pour aller le plus loin possible. Apres, il te faudra un supercalculateur.
Une place a Cambridge t'attend :-)

Merci poto tu exagères tjs!!

Je crois que je tiens qqchose là :

#include stdio.h
#include stdlib.h
#include time.h
#include math.h
#include sys/param.h
#include new

int main()
{

long int val,comptageNP=0;
int X,Y,test,affiche=0;
printf ( "Programme Personnel . \nVeuillez insérer un nombre limite en dessous duquel tous les nbres premiers seront calculés : " ) ;
scanf("%lu", &val);
printf(" Affichage Oui = 1 Non = 0 : ");
scanf(" %d", &affiche);
time_t debut = time(NULL);
X = val - (val % 6);
float* Tableau2 = new float [X/6];
Y=sqrt(X);

//TABLE MULTIPLICATIVE

for ( int i = 5 ; i <= Y; i = i + 2 )
{
if ( i % 3 == 0)
i = i+2 ;
If(i%5 ==0)
I = i+2;
for(int j=i ; i*j < X; j = j + 2)
{
if ( j % 3 == 0)
j = j+2 ;
If (j%5 ==0)
j =j+2;
if (i * j < X && (i*j -1)%6 ==0)
{
Tableau2[(i*j-1)/6]= Tableau2[(i*j -1)/6]+ 0.1;
printf("\n Tableau2[(%d × %d - 1)/6= %d/6 = %d] = %.1f",i,j,(i*j -1),(i*j -1)/6, Tableau2[(i*j-1)/6]);
}
else
{
Tableau2[(i*j+1)/6]= Tableau2[(i*j +1)/6]+ 1.0;
printf("\n Tableau2[(%d × %d +1)/6 = %d/6 = %d] = %.1f",i,j,(i*j +1),(i*j +1)/6, Tableau2[(i*j+1)/6]);
}
}
}

//printf(" \n Tableau2[20] = %f", Tableau2[20]);

time_t fin = time(NULL);
printf ("\n\n Temps de recherche : %ld secondes ", fin- debut);

/* J’AI MIS TOUTE LA SUITE EN COMMENTAIRES A PARTIR D’ICI


//AFFICHAGE ET COMPTAGE

for ( unsigned long int i = 5 , j = 7 ; i <= X ; i = i + 6 , j = j + 6 )
{
If (i%5 ==0)
i = i+6;
If (j%5==0)
j = j+6;
if (Tableau2[ i ] ==0)
{
comptageNP++;
if (affiche == 1)
printf("\n i = %lu", i);
}
if (Tableau2[ j ] ==0)
{
comptageNP++;
if (affiche == 1)
printf("\n j = %lu\t", j);
}
}

printf ("\n %d nombres premiers trouvés sur une recherche de 5 à \n%d",comptageNP,val);
boucle :
printf("\n\n\n tester la primalité d’un nombre ou entrez 0 pour sortir : ");
scanf("%d", &test);
system("cls");
if (test == 0)
return 0;
else if ( test == 2 || test ==3 )
{
printf("\n le nombre à%d est premier",test);
goto boucle;
}
else if (test % 2 ==0 || test % 3 ==0 || Tableau2[test]==1)
{
printf("\n le nombre %d est composé",test);
goto boucle;
}
else
{
printf (" le nombre %d est premier",test);
goto boucle;
}

*/
}

Screenshot_20240115-152833.jpg

Il me semble que dans l’affichage j’ai TOUT ici :
1/ Je divise l’espace mémoire du tableau en 6 à condition de choisir un typage en char sur 1 byte et non sur un float qui coûte 4 bytes.
2/ je garde la décomposition en facteurs premiers avant multiplication (ce qui entraînait une perte de l’information des que la multiplication etait calculée)........tu suis mon regard adhoc??
3/je connais de suite où sont les nombres premiers repérés par le nombre 0 situés d’un côté ou de l’autre du point (équivalent à la virgule de separation du nombre flottant.
4/ et tous les multiples sont marqués par une valeur positive donc différente de 0 situés aussi d’un côté où de l’autre du point ( équivalent ici à la virgule de separation du nombre flottant).
5/ Et je ne perd rien en vitesse de calcul tout en gagnant en espace de stockage.

C’est très rigolo ce truc.
Je vois ça dans la journée
Ps : Tous les nombres premiers sont représentés par l’écriture sous forme de tableaux[X] = 0.a ou bien a.0
et quand les tableaux n’existent pas sous la forme 0.0 c’est que je n’ai pas trouvé de multiples.
Tout Tableau manquant dans le listing est obligatoirement un tableau de nombres premiers jumeaux.
EXEMPLE : Il manque ici les Tableau2[1] .....puis Tableau2[2] .....puis Tableau2[3]
Ce qui correspond aux jumeaux 5-7 11-13 17-19 qui tournent autour des pivots respectifs
[1]×6 =6
[2]×6= 12
[3]×6= 18
Viens ensuite le Tableau2[4] = 0.1 qui donne
6×4=24 avec 23 premier correspondant au zéro à gauche du point représentant le chiffre pivot 24 et 25 multiple de 5 correspondant au 1 à droite du point pivot représentant toujours le chiffre pivot 24.
Ça peut être 1 ou 2 ou 3...... etc suivant le nombre de redondances rencontrées dans les tables de multiplication. Ces entiers positifs seront situés aussi bien à droite ou à gauche du point pivot mais on peut les rencontrer des 2 côtés à la fois si le programme a trouvé des multiples de chaque côté de n×6.
Voilà comment marche ce truc rigolo 🤑🤑🤑

Amuses toi bien:
https://www.online-cpp.com/Q3winf5C1y

adhoc

15/01/2024 à 08h55

Pas mal. et ca te permet d'aller jusqu'a combien, tu penses, a capacités memoires egales? Ta limite était 100M.

adhoc écrivait:
-----
> Pas mal. et ca te permet d'aller jusqu'a combien, tu penses, a capacités
> memoires egales? Ta limite était 100M.
Non je te corrige adhoc.... ma limite était de 900M.
Je sais pas il faut que je passe en tableau de caractères ou d’entier au maximum pour libérer de l’espace de stockage.
Je vois ça dans la journée. A+adhoc
(Dès que j’ai le résultat je le met de suite sur le fil aucun soucis)
Une première approche
Je gagne en stockage mémoire car l’ordi ne plante plus pour 1,4 Milliard (voir photo) mais je perd beaucoup en vitesse d’exécution et ça je ne m’y attendais pas !!!!!!
Je viens de gagner + de1 mn en condensant des lignes d’affectation . 🙃
Avant pour un tableau de 1 Milliard d’adressage sur 1 octet (bool) j’avais 1 Milliard d’octet d’occupation mémoire pour stocker l’info.
Avec les flottants je multiplie ce Milliard par 4 mais en contrepartie je n’ai besoin que du Sixième de l’espace mémoire.
Soit 1M x 4/6 = 0,66666
Je gagne 1/3 de mémoire en plus environ.
Avant je plantais à un peu plus de 0,9 Milliard.
Maintenant je bloque vers + de 1,4 Milliard.
J’avais depuis longtemps envie de virer les multiples de 5 comme tu me l’avais suggéré et j’ai gagné encore 1 seconde sur 100 Millions soit 2 secondes au lieu de 3.
Le seul problème c’est que les multiples de 5 ne sont pas marqués à 1 comme multiples.

C’est pour ça que sur le test nombre par nombre j’ai corrigé en reintroduisant un correctif. On peut pas tout avoir🤔🤔
Merci poto!

Voici le programme

#include stdio.h
#include stdlib.h
#include time.h
#include math.h
#include sys/param.h
#include new

int main()
{

long int val,comptageNP=0;
int dec=0 ;
int entier=0;
float flottant;
int X,Y,test,affiche=0;
printf ( "Programme Personnel . \nVeuillez insérer un nombre limite en dessous duquel tous les nbres premiers seront calculés : " ) ;
scanf("%lu", &val);
printf(" Affichage Oui = 1 Non = 0 : ");
scanf(" %d", &affiche);
time_t debut = time(NULL);
X = val - (val % 6);
float* Tableau2 = new float [X/6];
Y=sqrt(X);

//TABLE MULTIPLICATIVE

for ( int i = 5 ; i <= Y; i = i + 2 )
{
if ( i % 3 == 0)
i = i+2 ;
for(int j=i ; i*j < X; j = j + 2)
{
if ( j % 3 == 0)
j = j+2 ;
if (i * j < X && (i*j -1)%6 ==0)
{
Tableau2[(i*j-1)/6]= Tableau2[(i*j-1)/6]+ 0.1;
if (affiche == 1)
printf("\n Tableau2[(%d × %d - 1)/6= %d/6 = %d] = %.1f",i,j,(i*j -1),(i*j -1)/6, Tableau2[(i*j-1)/6]);
}
else
{
Tableau2[(i*j+1)/6]= Tableau2[(i*j +1)/6]+ 1.0 ;
if (affiche == 1)
printf("\n Tableau2[(%d × %d +1)/6 = %d/6 = %d] = %.1f",i,j,(i*j +1),(i*j +1)/6, Tableau2[(i*j+1)/6]);
}
}
}

time_t fin = time(NULL);
printf ("\n\n Temps de recherche : %ld secondes ", fin- debut);


//AFFICHAGE ET COMPTAGE
for ( int i = 1 ; i <= X/6; i = i + 1)
{
entier= (int)Tableau2[i];
flottant= Tableau2[i] ;
flottant = flottant*10;
dec= (int) flottant;
dec= dec%10;
if (entier == 0)
{
comptageNP++;
if (affiche == 1)
printf("\n % d est premier", i*6 -1);
}

if (dec == 0)
{
comptageNP++;
if (affiche == 1)
printf("\n % d est premier", i*6 +1);
}

}

printf ("\n\n %ld nombres premiers trouvés sur une recherche de 5 à %ld",comptageNP,val);

}

Dernière minute: je n’ai pas tous les np.
Après beaucoup de contrôles ça ne vient pas du procédé employé mais je dois implémenter 1 ou 2 conditions "if" pour éviter ce genre de pb. Je remet ça plus tard.
J’ai essayé de réduire le typage des tableaux pour passer de float à short int et ça plante très vite!!!!

https://www.online-cpp.com/1B6rlLxQfv

Screenshot_20240115-110903.jpg

Screenshot_20240115-174333.jpg