C ++ Sieve of Atkin可以忽略几个素数 [英] C++ Sieve of Atkin overlooks a few prime numbers
问题描述
最近我一直在使用C ++主要生成器，使用Atkin筛选器（ http：// en.wikipedia.org/wiki/Sieve_of_atkin ）以生成其素材。我的目标是能够生成任何32位数。我将主要用于项目euler问题。
Recently I've been working on a C++ prime generator that uses the Sieve of Atkin ( http://en.wikipedia.org/wiki/Sieve_of_atkin ) to generate its primes. My objective is to be able to generate any 32-bit number. I'll use it mostly for project euler problems. mostly it's just a summer project.
程序使用一个位板来存储素数：即一系列的1和0，例如第11位为1 ，第12个a 0和第13个a 1等。对于有效的内存使用，这实际上是字符数组，每个字符包含8位。我使用标志和按位操作符设置和检索位。算法的gyst很简单：使用一些方程式做第一次通过我不假装理解定义一个数字是否被认为是素数。这将获得正确的答案，但一对夫妇的非初级数字将被标记为素数。因此，当遍历列表时，您设置您刚刚发现的所有倍数的不是素数。
The program uses a bitboard to store primality: that is, a series of ones and zeros where for example the 11th bit would be a 1, the 12th a 0, and the 13th a 1, etc. For efficient memory usage, this is actually and array of chars, each char containing 8 bits. I use flags and bitwise-operators to set and retrieve bits. The gyst of the algorithm is simple: do a first pass using some equations I don't pretend to understand to define if a number is considered "prime" or not. This will for the most part get the correct answers, but a couple nonprime numbers will be marked as prime. Therefore, when iterating through the list, you set all multiples of the prime you just found to "not prime". This has the handy advantage of requiring less processor time the larger a prime gets.
我有90％完成，有一个catch：
一些缺少素数。
I've got it 90% complete, with one catch: some of the primes are missing.
通过检查板子，我已经确定在第一遍中省略了这些素数，基本上是为每个解决方案切换一个数字。维基百科条目）。我已经经历了这大块代码的时间和时间了。我甚至试图增加界限，在维基百科文章中显示，这是效率较低，但我想到可能会打几个数字，我已经以某种方式省略。没有什么工作。这些数字简单地评价为不是素数。在这个范围内，这些是被省略的素数：
Through inspecting the bitboard, I have ascertained that these primes are omitted during the first pass, which basically toggles a number for every solution it has for a number of equations (see wikipedia entry). I've gone over this chunk of code time and time again. I even tried increasing the bounds to what is shown in the wikipedia articles, which is less efficient but I figured might hit a few numbers that I have somehow omitted. Nothing has worked. These numbers simply evaluate to not prime. Most of my test has been on all primes under 128. Of this range, these are the primes that are omitted:
23和59。
我毫不怀疑，在更高的范围，更多的会丢失（只是不想通过他们所有）。我不知道为什么这些都缺失，但他们是。这两个素数有什么特别的吗？我有双重和三重检查，发现和修复错误，但它仍然可能是愚蠢的，我缺少。
I have no doubt that on a higher range, more would be missing (just don't want to count through all of them). I don't know why these are missing, but they are. Is there anything special about these two primes? I've double and triple checked, finding and fixing mistakes, but it is still probably something stupid that I am missing.
反正，这里是我的代码：
anyways, here is my 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;
}
}
我尽力把它清理干净可读。
I did my best to clean it up and make it readable. I'm not a professional programmer, so please be merciful.
这是我得到的输出，当我初始化一个名为pgen的PrimeGen对象时，用pgen打印它的初始位板.printBoard（）（请注意在next（）迭代之前缺少23和59），然后遍历next（）并打印所有返回的素：
Here is the output I get, when I initialize a PrimeGen object named pgen, print its initial bitboard with pgen.printBoard() (please note that 23 and 59 are missing before next() iteration), and then iterate through next() and print all of the returned primes:
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.
推荐答案
Eureka !!!
Eureka!!!
如我所料，这是一个愚蠢的错误。
As expected, it was a stupid error on my part.
3x ^ 2 - y ^ 2方程有一个小警告，忽略：x> y。考虑到这一点，我切换23和59太多次，导致他们失败。
The 3x^2 - y^2 equation has a small caveat that I overlooked: x > y. With this taken into account, I was switching 23 and 59 too many times, leading to them failing.
感谢所有的帮助，你们。保存了我的培根。
Thanks for all the help you guys. Saved my bacon.
这篇关于C ++ Sieve of Atkin可以忽略几个素数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
