标签: sieve-of-atkin

我在维基百科上读过关于阿特金的筛选,但维基目前是有限的.我正在寻找高水平的阿特金筛选和Java中的一个例子的解释.

谢谢.

我正在做一个项目,我需要一种有效的方法来计算素数.我使用了Eratosthenes的筛子,但是我一直在寻找并发现Atkin的筛子是一种更有效的方法.我发现很难找到这种方法的解释(我能够理解!).它是如何工作的？示例代码(最好是在C或python中)很棒.

编辑:感谢您的帮助,我唯一不理解的是x和y变量在伪代码中引用的内容.有人可以帮我解释一下吗？

我一直在努力学习生成素数的算法,我在维基百科上遇到了阿特金的Sieve.我理解算法的几乎所有部分,除了少数几个.以下是问题:

1. 下面的三个二次方程如何形成？4x ^ 2 + y ^ 2,3x ^ 2 + y ^ 2和3x ^ 2-y2
2. 维基百科中的算法讨论模数为60但我不明白在下面的psudocode中使用的方式/位置.
3. 如何找到这些提醒1,5,7和11？

以下是维基百科的伪代码供参考:

// arbitrary search limit                                                   
limit ? 1000000                                                             

// initialize the sieve                                                     
for i in [5, limit]: is_prime(i) ? false                                    

// put in candidate primes:                                                 
// integers which have an odd number of                                     
// representations by certain quadratic forms                               
for (x, y) in [1, ?limit] × [1, ?limit]:                                    
    n ? 4x²+y²                                                              
    if (n ? limit) and (n mod 12 = 1 or …

我已经实施了Atkin的Sieve,它的工作效果非常接近100,000,000左右.除此之外,它因内存问题而崩溃.

在算法中,我想用基于硬盘的阵列替换基于内存的阵列.Python的"wb"文件函数和Seek函数可以解决问题.在我发明新轮子之前,有人可以提供建议吗？一开始就出现两个问题:

1. 有没有办法将Atkin的Sieve"块"用于处理内存中的段,以及
2. 有没有办法暂停活动并稍后再回来 - 建议我可以序列化内存变量并恢复它们.

我为什么要这样做？寻找娱乐和保持面条工作的老geezer.

我想知道是否有人在这里有一个很好的实施他们想要分享的阿特金筛选.

我正在尝试实现它,但不能完全包围它.这是我到目前为止所拥有的.

public class Atkin : IEnumerable<ulong>
{
    private readonly List<ulong> primes;
    private readonly ulong limit;

    public Atkin(ulong limit)
    {
        this.limit = limit;
        primes = new List<ulong>();
    }

    private void FindPrimes()
    {
        var isPrime = new bool[limit + 1];
        var sqrt = Math.Sqrt(limit);

        for (ulong x = 1; x <= sqrt; x++)
            for (ulong y = 1; y <= sqrt; y++)
            {
                var n = 4*x*x + y*y;
                if (n <= limit && (n % 12 == 1 || n …

我知道可以实施Eratosthenes筛,以便在没有上限(分段筛)的情况下连续找到质数.

我的问题是,阿特金/伯恩斯坦的筛子能否以同样的方式实施？

相关问题:C#:如何制作Atkin增量扫描

然而,相关问题只有一个答案,即"所有筛子都不可能",这显然是不正确的.

我根据维基百科的低效但清晰的伪代码写了一篇非常天真的Atna Sieve实现.我最初在MATLAB中编写了算法,它省略了5作为素数.我也用Python编写了算法,结果相同.

从技术上讲,我知道为什么要排除5; 在步骤中n = 4*x^2 + y^2,当x == 1且y == 1时n == 5.这只发生一次,因此5从素数转换为非素数并且从不翻转.

为什么我的算法与维基百科上的算法不匹配？虽然我做了一些表面调整(例如,在每次迭代中只计算一次x ^ 2,在第一个等式中使用时存储mod(n,12)的值等),但它们不应该改变逻辑.算法.

我阅读了几篇 与阿特金筛选有关的讨论 ,但我不知道在我的实现中产生问题的区别是什么.

Python代码:

def atkin1(limit):
    res = [0] * (limit + 1)
    res[2] = 1
    res[3] = 1
    res[5] = 1

    limitSqrt = int(math.sqrt(limit))
    for x in range(1, limitSqrt+1):
        for y in range(1, limitSqrt+1):
            x2 = x**2
            y2 = y**2
            n = 4*x2 + y2
            if n == 5:
                print('debug1')
            nMod12 …

我不知道这是否可能，但我只是想问一下。我的数学和算法技能有点让我失望：P

问题是我现在有这个类可以生成达到一定限制的素数：

public class Atkin : IEnumerable<ulong>
{
    private readonly List<ulong> primes;
    private readonly ulong limit;

    public Atkin(ulong limit)
    {
        this.limit = limit;
        primes = new List<ulong>();
    }

    private void FindPrimes()
    {
        var isPrime = new bool[limit + 1];
        var sqrt = Math.Sqrt(limit);

        for (ulong x = 1; x <= sqrt; x++)
            for (ulong y = 1; y <= sqrt; y++)
            {
                var n = 4*x*x + y*y;
                if (n <= limit && (n % 12 == 1 || n …

最近我一直在研究使用Atve的Sieve(http://en.wikipedia.org/wiki/Sieve_of_atkin)生成其素数的C++素数生成器.我的目标是能够生成任何32位数字.我将主要用于项目的euler问题.大多数情况下,这只是一个夏季项目.

该程序使用一个位板来存储素数:即一系列的1和0,例如第11位将是1,第12位是0,第13位是1等.为了有效的内存使用,这实际上是和字符数组,每个字符包含8位.我使用标志和按位运算符来设置和检索位.该算法的陀螺很简单:使用我不假装理解的一些方程式进行第一次传递,以定义数字是否被认为是"素数".这将在很大程度上得到正确的答案,但一些非主要数字将被标记为素数.因此,在遍历列表时,将刚刚找到的素数的所有倍数设置为"非素数".这具有便利的优点,即需要较少的处理器时间,而素数越大.

我已经完成了90%,只有一个问题:一些素数缺失.

通过检查位板,我已经确定在第一次传递期间省略了这些素数,这基本上为每个方程式切换一个数字(参见维基百科条目).我一次又一次地浏览了这段代码.我甚至尝试增加维基百科文章中显示的界限,效率较低,但我想可能会打几个我已经忽略的数字.没有任何效果.这些数字只是评估为不是素数.我的大部分测试都是在128以下的所有质数下.在这个范围内,这些是省略的素数:

23和59.

我毫不怀疑,在更高的范围内,会有更多的缺失(只是不想计算所有这些).我不知道为什么缺少这些,但它们是.这两个素数有什么特别之处吗？我已经进行了两次和三次检查,发现并修复了错误,但是我仍然缺少一些愚蠢的东西.

无论如何,这是我的代码:

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

我对Atkin筛选的实施要么忽略接近极限的质数,要么忽略接近极限的复合材料.虽然有些限制有效,有些却没有.对于什么是错误,我完全感到困惑.

def AtkinSieve (limit):
results = [2,3,5]
sieve = [False]*limit
factor = int(math.sqrt(lim))
for i in range(1,factor):
    for j in range(1, factor):
        n = 4*i**2+j**2
        if (n <= lim) and (n % 12 == 1 or n % 12 == 5):
            sieve[n] = not sieve[n]
        n = 3*i**2+j**2
        if (n <= lim) and (n % 12 == 7):
            sieve[n] = not sieve[n]
        if i>j:
            n = 3*i**2-j**2
            if (n <= lim) and (n % 12 == …

我试图解决Project Euler问题10,其中要求用户计算少于200万的所有素数的总和.我通过研究维基百科上的伪代码写了以下内容,但它产生的答案似乎是不正确的,至少根据网站每当我尝试输入它时:

int main()
{
   int limit = 2000000;
   int answer = 5;

   std::vector<bool> isPrime;
   for( int i = 0; i < limit; ++i ){
      isPrime.push_back( false );
   }

   int n = 0;
   for( int x = 1; x <= ceil( sqrt( limit ) ); ++x ){
      for( int y = 1; y <= ceil( sqrt( limit ) ); ++y ){

         n = 4*x*x + y*y;
         if( (n <= limit) && ( n%12 == …