Atkin의 C++ Sieve는 몇 개의 소수를 간과합니다

Question

최근에 저는 Atkin의 체 (http://en.wikipedia.org/wiki/Sieve_of_atkin)를 사용하여 그 소수를 생성하는 C++ 소수 생성기에 대해 연구했습니다. 내 목표는 모든 32 비트 숫자를 생성 할 수있게하는 것입니다. 나는 주로 프로젝트 오일러 문제에 그것을 사용할 것이다. 대부분 여름 프로젝트 일뿐입니다.

이 프로그램은 소수성을 저장하기 위해 비트 보드를 사용합니다. 즉, 예를 들어 11 번째 비트가 1, 12 번째 0, 13 번째 1 등의 일련의 1과 0입니다. 효율적인 메모리 사용 , 이것은 실제로 char의 배열이며 각 char은 8 비트를 포함합니다. 플래그와 비트 연산자를 사용하여 비트를 설정하고 검색합니다. 알고리즘의 요점은 간단합니다. 몇 가지 방정식을 사용하여 첫 번째 단계를 수행합니다. 숫자가 "소수"로 간주되는지 정의하기 위해 이해하지 못한 척합니다. 대부분의 경우 정답을 얻을 수 있지만 소수의 소수점 이하 자릿수는 소수로 표시됩니다. 따라서 목록을 반복 할 때 방금 찾은 소수의 모든 배수를 "소수가 아닌"으로 설정합니다. 이것은 프라임이 커질수록 적은 프로세서 시간을 요구하는 편리한 이점이 있습니다.

저는 하나의 캐치로 90 % 완성되었습니다. 소수의 일부가 누락되었습니다.

비트 보드를 검사하여 첫 번째 단계에서이 소수가 생략되었음을 확인했습니다.이 소수는 기본적으로 여러 방정식에 대한 모든 솔루션의 번호를 토글합니다 (위키 백과 항목 참조). 이 코드를 여러 번 반복했습니다. 나는 위키 피 디아의 기사에 나와있는 범위를 늘리려고 시도했는데, 덜 효과적 이었지만, 어떻게 든 생략 된 몇 가지 숫자를 쳤을지도 모른다. 아무것도 효과가 없습니다. 이 숫자는 단순히 소수가 아닌 것으로 평가됩니다.

23 및 59

을 나는 더 높은 범위에 이상이 누락 될 것이라고 의심의 여지가 : 내 테스트의 대부분이 범위의 128 아래에있는 모든 소수에있다,이 생략 된 소수입니다 (단지 모든 것을 헤치고 싶지는 않습니다). 나는 왜 이것이 빠졌는지 모르지만 그렇습니다. 이 두 소수에 특별한 것이 있습니까? 나는 이중 및 삼중 검사를하고, 실수를 찾아 내었지만, 여전히 내가 빠진 무언가 어리 석다.

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

나는 그것을 청소하고 읽을 수 있도록 최선을 다했다 :

어쨌든, 여기 내 코드입니다. 나는 전문 프로그래머가 아니므로 자비를 베풀어주십시오.

다음은 pgen이라는 PrimeGen 객체를 초기화 할 때 pgen.printBoard()를 사용하여 초기 비트 보드를 인쇄합니다 (다음() 반복 전에 23 및 59가 누락되었음을 유의하십시오). next() 그리고 반환 된 모든 소수를 출력 :

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

유레카 !!!

예상대로 내 부분에서는 어리석은 오류입니다.

3x^2 - y^2 방정식에는 x> y를 간과 한 작은주의 사항이 있습니다. 이를 고려하여 나는 23 번과 59 번을 너무 많이 번갈아 가며 실패로 이끌었다.

여러분 모두 도와 주셔서 감사합니다. 내 베이컨을 구 했어.