C ++ Crivello di Atkin si affaccia un paio di numeri primi

Question

Di recente ho lavorato su un C ++ primo generatore che utilizza il crivello di Atkin ( http: / /en.wikipedia.org/wiki/Sieve_of_atkin ) per generare i suoi numeri primi. Il mio obiettivo è quello di essere in grado di generare qualsiasi numero a 32 bit. Io lo uso principalmente per problemi di Project Euler. la maggior parte è solo un progetto estivo.

Il programma usa un bitboard per memorizzare primalità: cioè, una serie di uno e zero dove per esempio il bit 11 sarà un 1, il 12 un 0, e il 13 un 1, ecc Per utilizzo efficiente della memoria, questo è in realtà e array di caratteri, ogni carattere contiene 8 bit. Io uso bandiere e bit a bit-operatori per impostare e recuperare i bit. La gyst dell'algoritmo è semplice: fare un primo passaggio utilizzando alcune equazioni non pretendo di capire per definire se un numero è considerato "prime" o meno. Questo sarà per la maggior parte ottenere le risposte corrette, ma un paio di numeri non-prime saranno contrassegnati come primo. Pertanto, quando scorrendo la lista, è possibile impostare tutti i multipli del Primo hai appena trovato a "Not Prime". Questo ha il pratico vantaggio di richiedere meno tempo di processore più grande è un primo ottiene.

li ho il 90% completo, con un problema: alcuni dei numeri primi sono mancanti.

Attraverso ispezionare il bitboard, ho accertato che questi numeri primi vengono omessi durante il primo passaggio, che alterna fondamentalmente un numero per ogni soluzione ha un numero di equazioni (vedi voce wikipedia). Ho passato su questo pezzo di tempo codice e più volte. Ho anche provato aumentando i limiti di ciò che viene mostrato negli articoli di Wikipedia, che è meno efficiente, ma ho pensato che potrebbe colpire alcuni numeri che ho in qualche modo omesso. Niente ha funzionato. Questi numeri semplicemente valutano di non primo. La maggior parte del mio test è stato in tutti i primi sotto 128. Di questa gamma, questi sono i numeri primi che vengono omessi:

23 e 59.

Non ho alcun dubbio sul fatto che su una gamma più alta, più sarebbero mancanti (solo che non voglio contare attraverso tutti loro). Non so il motivo per cui questi mancano, ma sono. C'è qualcosa di speciale in questi due numeri primi? Ho doppie e triple controllato, trovare e correggere gli errori, ma è ancora probabilmente qualcosa di stupido che mi manca.

In ogni modo, qui è il mio codice:

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

Ho fatto del mio meglio per ripulirlo e renderlo leggibile. Io non sono un programmatore professionista, quindi cerca di essere misericordioso.

Ecco l'output ricevo, quando ho inizializzare un oggetto di nome PGEN PrimeGen, stampare la sua bitboard iniziale con pgen.printBoard () (si prega di notare che il 23 e 59 sono dispersi prima della prossima iterazione ()), e poi scorrere prossimo () e stampare tutti i numeri primi restituiti:

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 !!!

Come previsto, è stato un errore stupido da parte mia.

Il ^ 2 3x - y ^ 2 equazione ha una piccola avvertenza che ho trascurato: x> y. Con questa presa in considerazione, sono stato il passaggio 23 e 59 troppe volte, portando a loro meno.

Grazie per tutto l'aiuto voi ragazzi. Salvato la mia pancetta.