Optimisation d’un crible d’Erathostene en C

bonjour,

je me demande pourquoi tu as mis ce IF à l'intérieur du FOR:

                             for (int n =0 ;  X*(X+2*n)< val ; n++)
                               {
                                 if (!(Tab[X / 8] & (1 << (X % 8))))

Tu pourrais essayer de remplacer les divisions par 8 par un décalage de 3 (x >> 3) et les modulo 8 par un masque (x & 7)

Le truc pour sauver de la mémoire est bon, mais ton algo est loin d'être le meilleur.

Tu en trouveras de meilleurs en cherchant sur Internet.

J'ai pris la peine de tester ton code et il ne fonctionne définitivement pas.
Pour 100, j'obtiens plus d'une valeur suivant les tests. Ça varie de 26 à 29.
Il est évident que tu accèdes à une zone de mémoire non initialisée.
Avant de chercher à optimiser, il faut commencer par faire fonctionner le code.
Ton approche avec le GOTO est plutôt mauvaise.
Tu n'as besoin que de deux boucles FOR imbriquées avec un IF pour savoir si le nombre suivant est premier.

Que nenni mon algo fonctionne!!!

Voir ici :

https://www.mycompiler.io/view/4hYfMMdgMIf

Rentrer val= 80000000 maxi

Même programme en JScript
https://reduction-image.com/eugenol/Premiers_allocation_memoireJS.html
Rechercher pour 2500000000
Temps de recherche : 75893 millisecondes
On a trouvé 121443370 nombres premiers

Bonjour, il y a plusieurs "erreurs".

Attention au GoTo. Tu peux utiliser un simple "if".

Je te propose ce que tu as demandé.

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int main() {
    int val;
    printf("\n(Programme Grifix - recherche des nombres premiers optimisé)\nInsérez la valeur sup de vos nombres : ");
    scanf("%d", &val);

    // Allocation de mémoire pour le tableau de bits
    unsigned char *Tab = (unsigned char *)calloc((val + 7) / 8, sizeof(unsigned char));
    if (Tab == NULL) {
        printf("Erreur d'allocation de mémoire\n");
        return 1;
    }

    int X = 3;
    int nombre_de_premiers = 1; // On compte '2' comme premier
    time_t debut = time(NULL);

    // Parcours des nombres impairs pour marquer les non-premiers
    for (X = 3; X * X <= val; X += 2) {
        // Si X est un nombre premier (non marqué)
        if (!(Tab[X / 8] & (1 << (X % 8)))) {
            // Marquer les multiples impairs de X à partir de X*X
            for (int n = X * X; n < val; n += 2 * X) {
                Tab[n / 8] |= (1 << (n % 8));
            }
        }
    }

    // Calcul du nombre de premiers
    for (int i = 3; i < val; i += 2) {
        if ((Tab[i / 8] & (1 << (i % 8))) == 0) {
            nombre_de_premiers++;
        }
    }

    time_t fin = time(NULL);
    printf("\nTemps de recherche : %ld secondes\n", fin - debut);
    printf("On a trouvé %d nombres premiers\n", nombre_de_premiers);

    free(Tab); // Libération de la mémoire allouée
    return 0;
}

 N'hésite pas à revenir si tu veux des explications.

Puisqu'on tolère les solutions, voici la mienne.
Non, je ne suis pas "monsieur" PierrotLeFou. :)
 

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <time.h>
#define uchar unsigned char
// J'utilise size_t au lieu de uint64
int main(void) {
    time_t begin = time(NULL);
    uchar mask[8] = {1, 2, 4, 8, 16, 32, 64, 128};
    for(int i = 0; i < 8; i++) mask[i] = ~mask[i];     // J'inverse pour favoriser la boucle intérieure.
    size_t max;
    printf("Entrez le maximum ");
    scanf("%lld", &max);
    size_t size = (max+8) >> 3;     // Le maximum est inclus.
    uchar *tab = malloc(size);
    if(tab == NULL) {
        perror("malloc");
        fprintf(stderr, "Requested: %lld\n", size);
        exit(EXIT_FAILURE);
    }
    memset(tab, 0xff, size);     // Des 1 partout.
    size_t r = sqrt(max);     // Si max est plus grand que 2^53, il se peut que r soit incorrect.
    for(size_t n = 3; n <= r; n += 2) {
        if(tab[n>>3] & ~mask[n&7]) {
            for(size_t i = n*n; i <= max; i += n<<1) tab[i>>3] &= mask[i&7];
        }
    }
    for(size_t n = max+1; n < size*8; n++) tab[n>>3] &= mask[n&7];     // J'efface la fin du  dernier octet.
    uchar many[256];     // Pour compter le nombre de bits dans chaque octets.
    uchar msk = 2 + 8 + 32 + 128;     // Je garde les bits en positions impaires seulement.
    for(int i = 0; i < 256; i++) {
        uchar b = i & msk;
        uchar c = 0;
        for(int s = 0; s < 4; s++) {
            b >>= 1;
            c += b &1;
            b >>= 1;
        }
        many[i] = c;
    }
    size_t count = 0;     // Le 1 n'est pas effacé, il comptera pour le 2.
    for(int n = 0; n < size; n++) {
        count += many[tab[n]];     // On divise environ par 4 le nombre d'opérations.
    }
    printf("%ld millisecondes\n", time(NULL) - begin);
    printf("%lld\n", count);
    free(tab);
    return EXIT_SUCCESS;
}