C ++ Crible d'Atkin donne quelques nombres premiers

Question

Récemment, je travaille sur un C ++ générateur qui utilise le premier Crible d'Atkin ( http: / /en.wikipedia.org/wiki/Sieve_of_atkin ) pour générer les nombres premiers. Mon objectif est d'être en mesure de générer un nombre de 32 bits. Je vais l'utiliser principalement pour des problèmes euler du projet. la plupart du temps, il est juste un projet d'été.

Le programme utilise un bitboard pour stocker primalité: à savoir, une série de uns et de zéros, où par exemple le 11 bit serait 1, le 12 0, et le 13 un 1, etc. Pour une utilisation efficace de la mémoire, ceci est en fait et tableau de caractères, chaque carbonisation contenant 8 bits. J'utilise des drapeaux et des opérateurs-bitwise pour définir et récupérer les bits. Le gyst de l'algorithme est simple: faire une première passe en utilisant des équations, je ne prétends pas comprendre pour définir si un nombre est considéré comme « prime » ou non. Ce sera pour la plupart obtenir les bonnes réponses, mais quelques numéros seront marqués horaires secondaires comme premier choix. Par conséquent, lorsque vous parcourez la liste, vous définissez tous les multiples du premier que vous venez de trouver à « non prime ». Ceci a l'avantage pratique d'exiger moins de temps processeur Plus un premier obtient.

Je l'ai terminé à 90%, avec un cran: certains des nombres premiers sont portés disparus.

Grâce à l'inspection de la bitboard, j'ai constaté que ces nombres premiers sont omis lors du premier passage, ce qui permet de basculer essentiellement un numéro pour toutes les solutions qu'il a pour un certain nombre d'équations (voir l'entrée wikipedia). Je suis allé sur ce morceau de temps de code et encore. J'ai même essayé d'augmenter les limites de ce qui est indiqué dans les articles wikipedia, ce qui est moins efficace, mais je me suis peut frapper quelques chiffres que je l'ai en quelque sorte omis. Rien n'a fonctionné. Ces chiffres évaluent simplement pas premier. La plupart de mon test a été sur tous les nombres premiers en 128. De cette gamme, ce sont les nombres premiers qui ont été omis:

23 et 59.

Je ne doute pas que sur une gamme plus élevée, plus il manquerait (ne veux pas compter par chacun d'eux). Je ne sais pas pourquoi ils sont absents, mais ils sont. Y at-il quelque chose de spécial au sujet de ces deux nombres premiers? J'ai double et triple vérification, trouver et corriger les erreurs, mais il est sans doute encore quelque chose de stupide que je suis absent.

De toute façon, voici mon code:

#include <iostream>
#include <limits.h>
#include <math.h>

using namespace std;

const unsigned short DWORD_BITS = 8;

unsigned char flag(const unsigned char);
void printBinary(unsigned char);


class PrimeGen
{
    public:
        unsigned char* sieve;
        unsigned sievelen;
        unsigned limit;
        unsigned bookmark;


        PrimeGen(const unsigned);

        void firstPass();
        unsigned next();

        bool getBit(const unsigned);
        void onBit(const unsigned);
        void offBit(const unsigned);
        void switchBit(const unsigned);

        void printBoard();
};


PrimeGen::PrimeGen(const unsigned max_num)
{
    limit = max_num;
    sievelen = limit / DWORD_BITS + 1;
    bookmark = 0;

    sieve = (unsigned char*) malloc(sievelen);
    for (unsigned i = 0; i < sievelen; i++) {sieve[i] = 0;}

    firstPass();
}


inline bool PrimeGen::getBit(const unsigned index)
{
    return sieve[index/DWORD_BITS] & flag(index%DWORD_BITS);
}


inline void PrimeGen::onBit(const unsigned index)
{
    sieve[index/DWORD_BITS] |= flag(index%DWORD_BITS);
}


inline void PrimeGen::offBit(const unsigned index)
{
    sieve[index/DWORD_BITS] &= ~flag(index%DWORD_BITS);
}


inline void PrimeGen::switchBit(const unsigned index)
{
    sieve[index/DWORD_BITS] ^= flag(index%DWORD_BITS);
}


void PrimeGen::firstPass()
{
    unsigned nmod,n,x,y,xroof, yroof;

    //n = 4x^2 + y^2
    xroof = (unsigned) sqrt(((double)(limit - 1)) / 4);
    for(x = 1; x <= xroof; x++){
        yroof = (unsigned) sqrt((double)(limit - 4 * x * x));
        for(y = 1; y <= yroof; y++){
            n = (4 * x * x) + (y * y);
            nmod = n % 12;
            if (nmod == 1 || nmod == 5){
                switchBit(n);
            }
        }
    }

    xroof = (unsigned) sqrt(((double)(limit - 1)) / 3);
    for(x = 1; x <= xroof; x++){
        yroof = (unsigned) sqrt((double)(limit - 3 * x * x));
        for(y = 1; y <= yroof; y++){
            n = (3 * x * x) + (y * y);
            nmod = n % 12;
            if (nmod == 7){
                switchBit(n);
            }
        }
    }

    xroof = (unsigned) sqrt(((double)(limit + 1)) / 3);
    for(x = 1; x <= xroof; x++){
        yroof = (unsigned) sqrt((double)(3 * x * x - 1));
        for(y = 1; y <= yroof; y++){
            n = (3 * x * x) - (y * y);
            nmod = n % 12;
            if (nmod == 11){
                switchBit(n);
            }
        }
    }
}


unsigned PrimeGen::next()
{
    while (bookmark <= limit)
    {
        bookmark++;

        if (getBit(bookmark))
        {
            unsigned out = bookmark;

            for(unsigned num = bookmark * 2; num <= limit; num += bookmark)
            {
                offBit(num);
            }

            return out;
        }
    }

    return 0;
}


inline void PrimeGen::printBoard()
{
    for(unsigned i = 0; i < sievelen; i++)
    {
        if (i % 4 == 0)
            cout << endl;

        printBinary(sieve[i]);
        cout << " ";
    }
}


inline unsigned char flag(const unsigned char bit_index)
{
    return ((unsigned char) 128) >> bit_index;
}


inline void printBinary(unsigned char byte)
{
    unsigned int i = 1 << (sizeof(byte) * 8 - 1);

    while (i > 0) {
        if (byte & i)
            cout << "1";
        else
            cout << "0";
        i >>= 1;
    }
}

Je l'ai fait de mon mieux pour le nettoyer et le rendre lisible. Je ne suis pas un programmeur professionnel, donc s'il vous plaît être miséricordieux.

Voici la sortie que je reçois, quand j'initialisez un objet PrimeGen nommé Pgen, imprimer sa bitboard initiale avec pgen.printBoard () (s'il vous plaît noter que 23 et 59 sont portées disparues avant la prochaine itération ()), puis itérer suivant () et imprimer tous les nombres premiers retournés:

00000101 00010100 01010000 01000101
00000100 01010001 00000100 00000100
00010001 01000001 00010000 01000000
01000101 00010100 01000000 00000001

5
7
11
13
17
19
29
31
37
41
43
47
53
61
67
71
73
79
83
89
97
101
103
107
109
113
127

DONE

Process returned 0 (0x0)   execution time : 0.064 s
Press any key to continue.

Answer 1

Eureka !!!

Comme prévu, ce fut une erreur stupide de ma part.

3 x ^ 2 - y ^ 2 équation a une petite mise en garde que je négligé: x> y. Avec cette prise en compte, je commutation 23 et 59 trop de fois, ce qui conduit à leur défaut.

Merci pour l'aide que vous les gars. Sauvé le bacon.