Pourquoi ce code ne fait-il pas son travail?

Question

Je veux créer un programme qui écrit tous les nombres premiers dans un fichier (je sais qu'il existe un algorithme populaire "Sieve of Eratosthenes", mais j'essaie de le faire par moi-même). J'essaye d'éliminer toutes les complications pour les octets qui ont encore la valeur 1 puis les écris dans un fichier.

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

void afficher_sur_un_ficher (FILE* ficher, int nb_bit); 
char el_mask (int x); 

int main() 
{ 
    FILE* p_fich; 
    char tab[4096], mask, eli_mask; 
    int nb_bit = 0, x, f; 

    for (int i = 0; i < 4096; i++) 
    { 
     tab[i] = 0xff; 
    } 

    for (int i = 0; i < 4096; i++) 
    { 
     for (mask = 0x01; mask != 0; mask <<= 1) 
     { 
      if ((tab[i] & mask) != 0) 
      { 
       x = nb_bit; 
       while ((x > 1) && (x < 16384)) 
       { 
        eli_mask = el_mask (x); 
        f = x/8; 
        tab[f] = tab[f]^eli_mask; 
        x = x + nb_bit; 
       } 
       afficher_sur_un_ficher (p_fich, nb_bit); 
      } 
      nb_bit++; 
     } 
    } 
    system ("PAUSE"); 
    return 0; 
} 

void afficher_sur_un_ficher (FILE* ficher, int nb_bit) 
{ 
    ficher = fopen ("res.txt", "a+"); 
    fprintf (ficher, "%d \t", nb_bit); 
    int static z; 
    z = z + 1; 
    if (z % 10 == 0) 
     fprintf (ficher, "\n"); 
    fclose (ficher); 
} 

char el_mask (int x) 
{ 
    x = x % 8; 
    switch (x) 
    { 
     case 0: 
      x = 0b00000001; 
     break; 
     case 1: 
      x = 0b00000010; 
     break; 
     case 2: 
      x = 0b00000100; 
     break; 
     case 3: 
      x = 0b00001000; 
     break; 
     case 4: 
      x = 0b00010000; 
     break; 
     case 5 : 
      x = 0b00100000; 
     break; 
     case 6 : 
      x = 0b01000000; 
     break; 
     case 7: 
      x = 0b10000000; 
     break; 
    } 
    return x; 
} 

Answer 1

Il semble y avoir un problème dans la boucle qui essaie de dégager bits indiquant les non-nombres premiers:

while ((x > 1)&&(x < 16384)) 
{ 
    tab[i] = tab[i]^mask ; 
    x = x * 2 ; 
} 

Depuis i ne change pas dans cette boucle, vous essentiellement basculer le même bit de et tout en incrémentant x. En plus de corriger l'index en tab[], vous voudrez probablement changer l'opération de xor (^) en quelque chose qui effacera le bit inconditionnellement - une fois qu'un bit est effacé, vous ne voulez pas le traiter de nouveau pour un facteur différent 'réinitialiser' le bit. Notez qu'un incrément simple de i ne fera pas, car les multiples de x dans d'autres éléments de tab pourraient ne pas être dans le même décalage de bits (en effet, un seul élément de tab[] pourrait contenir plusieurs multiples de x).

Même si vous résolvez ce problème, je pense que la boucle pourrait ne pas faire ce que vous attendez, puisque x = x * 2; ne marche pas x à travers ses multiples - vous finirez par sauter certains non-primes.

Des recherches sur le fonctionnement du tamis d'Ératosthène pourraient être utiles.

Answer 2

Peut-être que je "m manque quelque chose, mais cela semble juste bancal. Je ne me souviens pas des algorithmes principaux courants de main gauche, mais, par exemple,

(excerpts) tab[i] = 0xff ; mask = 0x01 ;

for (int j = 0 ; j < 8 ; j++) { if ((tab[i] & mask) != 0) mask = mask<<1 ;

Cela signifie que vous serez toujours aller 8 fois - alors pourquoi vérifier avec le '&'

un autre,

x = nb_bit ; while ((x > 1)&&(x < 16384)) { tab[i] = tab[i]^mask ; x = x * 2 ; }

?

Cela retourne simplement les bits à chaque itération. Est-ce que c'est ce que tu veux? Enfin, comme je ne sais pas ce que vous voulez faire, attention à la longueur de vos objets. Vous pourriez BASCULE

0000 0000 1111 1111^0000 0001

ou

1111 1111 1111 1111^0000 00001

Comme je ne comprends pas vraiment ce que vous essayez de faire, pas sûr que cela puisse être lié.

EDIT (après le commentaire de Hamza):

Oui.Qu'est-ce que cette boucle fait est la suivante - comparer/'et'

avec

 0000 0001 
     0000 0010 
     0000 0100, 

et sera toujours vrai. Je ne sais pas ce que vous voulez faire ici, mais cela semble louche (changement de lieu maintenant sans internet pendant un certain temps, mais gl. :)).

Answer 3

Vous pouvez simplifier votre fonction principale un peu:

int main (int argc, char** argv) { 
    FILE* p_fich; 
    char tab[4096] , mask; 
    int nb_bit = 0 , x; 

    memset(tab, 0xFF, 4096); 
    for (int i = 0; i < 4096; i++) { 
     for (mask = 0x01; mask != 0; mask <<= 1) { 
      if ((tab[i] & mask) != 0) { 
       for (x = nb_bit; (x > 1) && (x < 0x4000), x<<=1) 
        tab[i] ^= mask; 
       afficher_sur_un_ficher (p_fich, nb_bit); 
      } 
      nb_bit++; 
     } 
    } 
    system ("PAUSE"); 
    return 0; 
} 

Maintenant, pour répondre à votre question: Votre fonction afficher_sur_un_ficher imprime tout ce que vous passez à lui, et que la fonction est appelée à chaque itération de la boucle où ((tab[i] & mask) != 0) est vrai. Puisque vous initialisez tous les octets tab[i] à 0xFF, le masquage d'une combinaison de bits donnée entraîne toujours l'évaluation de if par true. Vous modifiez la valeur de tab[i], mais une fois que vous le faites, vous n'utilisez plus ce bit, donc cela ne change pas le fait que l'instruction if sera toujours prise. C'est pourquoi vous voyez toutes les entrées enregistrées.

Edit: Si vous simplifiez pas tout le code qui ne touche pas la décision de sortie ou la valeur à la sortie, vous finissez par ce qui suit:

memset(tab, 0xFF, 4096); 
for (int i = 0; i < 4096; i++) { 
    for (mask = 0x01; mask != 0; mask <<= 1) { 
     afficher_sur_un_ficher (p_fich, nb_bit); 
     nb_bit++; 
    } 
} 

Comme vous pouvez le voir, cette code imprimera une séquence incrémentante d'entiers (0 à (4096 * 8) -1) et est complètement indépendant du tableau tab et des valeurs spécifiques de i et mask. Je pense qu'il manque quelque chose dans votre implémentation de l'algorithme. Avez-vous un lien vers une description de l'algorithme que vous essayez de mettre en œuvre? Ou est-ce un algorithme que vous avez développé? (Désolé, je n'ai pas compris votre description de votre algorithme que vous avez ajouté à la question)