-1

我想创建一个将所有素数写入文件的程序(我知道有一种流行的算法“埃拉托色尼筛法”,但我正在尝试自己制作)。我试图消除仍然具有值 1 的字节的所有复杂性,然后将它们写入文件中。

#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;
}
4

3 回答 3

5

尝试清除指示非素数的位的循环中似乎存在问题:

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

由于i在这个循环中没有改变,你基本上在增加x. 除了将索引固定为 之外tab[],您可能还希望将操作从 xor ( ^) 更改为无条件清除该位的操作 - 一旦清除某个位,您不希望再次处理该位以获得不同的因素以“重置” '一点。请注意,不会做一个简单的增量,因为其他元素中i的倍数可能不在同一个位偏移中(实际上,单个元素可能包含多个倍数)。xtabtab[]x

即使你解决了这个问题,我认为循环可能不会像你期望的那样做,因为x = x * 2;它没有x遍历它的倍数——你最终会跳过一些非素数。

一些关于“埃拉托色尼筛”工作原理的研究可能会有所帮助。

于 2010-04-14T00:13:35.950 回答
1

您可以稍微简化一下主要功能:

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;
}

现在,为了解决您的问题:您的afficher_sur_un_ficher函数将打印您传递给它的任何内容,并且在每次循环迭代中调用该函数,如果((tab[i] & mask) != 0)为真。tab[i]由于您将每个字节初始化为0xFF,因此屏蔽任何给定的位组合将始终导致该if语句进行评估true。您正在更改 的值tab[i],但是一旦这样做,您将不再使用该位,因此它不会改变该if语句将始终被采用的事实。这就是您看到每个条目都被记录的原因。

编辑: 如果您简化所有不影响输出决定或输出值的代码,您最终会得到以下结果:

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++;
    }
}

如您所见,此代码将打印一个递增的整数序列(0 到 (4096*8)-1),并且完全独立于数组和andtab的特定值。我认为您的算法实现中缺少一些东西。你有一个链接到你试图实现的算法的描述吗?或者这是您开发的算法?(抱歉,我不明白您对添加到问题中的算法的描述)imask

于 2010-04-14T00:41:58.080 回答
1

也许我错过了一些东西,但这似乎很不稳定。我不记得常用的素数算法,但是,例如,

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

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

这意味着你总是会去 8 次 - 那么为什么要检查 '&' 呢?

另一个,

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

这只是在每次迭代中翻转位。那是你要的吗?

最后,由于我不知道您的意思,请注意对象的位长度。你可能会翻牌

0000 0000 1111 1111 ^ 0000 0001

或者

1111 1111 1111 1111 ^ 0000 00001

由于我不太了解您要做什么,因此不确定这是否相关。

编辑(在哈姆扎的评论之后):

是的。这个循环的作用如下 - compare/'and'

1111 1111 1111 1111

      0000 0001
      0000 0010
      0000 0100,

这将永远成立。我不知道你想在这里做什么,但这似乎很可疑(现在改变位置,暂时没有互联网,但是 gl. :) )。

于 2010-04-14T00:32:05.347 回答