相关疑难解决方法(0)

这是我能提出的最佳算法.

def get_primes(n):
    numbers = set(range(n, 1, -1))
    primes = []
    while numbers:
        p = numbers.pop()
        primes.append(p)
        numbers.difference_update(set(range(p*2, n+1, p)))
    return primes

>>> timeit.Timer(stmt='get_primes.get_primes(1000000)', setup='import   get_primes').timeit(1)
1.1499958793645562

可以做得更快吗？

此代码有一个缺陷:由于numbers是无序集,因此无法保证numbers.pop()从集中删除最小数字.然而,它对某些输入数字起作用(至少对我而言):

>>> sum(get_primes(2000000))
142913828922L
#That's the correct sum of all numbers below 2 million
>>> 529 in get_primes(1000)
False
>>> 529 in get_primes(530)
True

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

谢谢.

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

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

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