我想知道是否有人在这里有一个很好的实现阿特金的筛的，他们想与大家分享。

我想实现它，但不能完全环绕它我的头。以下是我有这么远。

 公共类阿特金：IEnumerable的＆LT; ULONG＆GT;
{
    私人只读表＆LT; ULONG＆GT;素数;
    私人只读ULONG限制;

    公共阿特金（ULONG限制）
    {
        this.limit =限制;
        素数=新的名单，其中，ULONG＆GT;（）;
    }

    私人无效FindPrimes（）
    {
        VAR isPrime =新布尔[上限+ 1];
        VAR开方=的Math.sqrt（限制）;

        对于（ULONG X = 1; X＆LT; =开方; X ++）
            对于（ULONG Y = 1; Y＆LT; =开方; Y ++）
            {
                变种N = 4 * X * X + Y * Y;
                如果（正＆其中; =极限和安培;及（N％12 == 1 || N％12 == 5））
                    isPrime [N] ^ = TRUE;

                N = 3 * X * X + Y * Y;
                如果（N＆LT; =极限和放大器;＆安培; N％12 == 7）
                    isPrime [N] ^ = TRUE;

                N = 3 * X * X  -  Y *ÿ;
                如果（X＆GT; Y＆安培;＆安培; N＆LT; =极限和放大器;＆安培; N％12 == 11）
                    isPrime [N] ^ = TRUE;
            }

        对于（ULONG N = 5; N＆LT; =开方; N ++）
            如果（isPrime [n]）的
                对于（ULONG K = N * N; K＆LT; =限制; K * = K）
                    isPrime [K] = FALSE;

        primes.Add（2）;
        primes.Add（3）;
        对于（ULONG N = 5; N＆LT; =限制; N ++）
            如果（isPrime [n]）的
                primes.Add（N）;
    }


    公众的IEnumerator＆LT; ULONG＆GT;的GetEnumerator（）
    {
        如果（！primes.Any（））
            FindPrimes（）;


        的foreach（在VAR素数P）
            得到的回报磷;
    }


    IEnumerator的IEnumerable.GetEnumerator（）
    {
        返回的GetEnumerator（）;
    }
}
 

我有pretty的简单，只是想翻译列出的维基百科，但它不能正常工作。所以，无论是我误解的东西或者只是做了一些错误。或者最有可能的两个...

有第500素数，我作为测试使用的名单，我无法实现在40号（或41？）。

值在指数[40] 不同     预计：179     但是为：175

您能够找到我的错误，你有一个实现奠定左右，你可以分享，或两者兼而有之？

确切的测试我使用看起来像这样：

 公共抽象类AtkinTests
{
    [测试]
    公共无效GetEnumerator_FirstFiveHundredNumbers_AreCorrect（）
    {
        无功序列=新的阿特金（2000000）;
        变种实际= sequence.Take（500）.ToArray（）;
        VAR预期= First500;

        CollectionAssert.AreEqual（预期，实际值）;
    }

    私人静态只读ULONG [] First500 =新ULONG []
        {
            2，3，5，7，11，13，17，...
        };
}
 

解决方案

这code：

 的（ULONG K = N * N; K＆LT; =限制; K * = K）
  isPrime [K] = FALSE;
 

似乎并没有成为这种伪code忠实的翻译：

  is_prime（K）←假，K∈{N²，2n²，3n²，...，限}
 

您code看起来像它会运行N * N，N- ^ 4，N ^ 8等即每平方时间，而不是添加正平方各一次。试试这个：

  ULONG nSquared = N * N;
对于（ULONG K = nSquared; K＆LT; =限制; K + = nSquared）
  isPrime [K] = FALSE;
 

I was wondering if someone here have a good implementation of the Sieve of Atkin that they would like to share.

I am trying to implement it, but can't quite wrap my head around it. Here is what I have so far.

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 % 12 == 5))
                    isPrime[n] ^= true;

                n = 3*x*x + y*y;
                if (n <= limit && n % 12 == 7)
                    isPrime[n] ^= true;

                n = 3*x*x - y*y;
                if (x > y && n <= limit && n % 12 == 11)
                    isPrime[n] ^= true;
            }

        for (ulong n = 5; n <= sqrt; n++)
            if (isPrime[n])
                for (ulong k = n*n; k <= limit; k *= k)
                    isPrime[k] = false;

        primes.Add(2);
        primes.Add(3);
        for (ulong n = 5; n <= limit; n++)
            if (isPrime[n])
                primes.Add(n);
    }


    public IEnumerator<ulong> GetEnumerator()
    {
        if (!primes.Any())
            FindPrimes();


        foreach (var p in primes)
            yield return p;
    }


    IEnumerator IEnumerable.GetEnumerator()
    {
        return GetEnumerator();
    }
}

I have pretty much just tried to "translate" the pseudocode listed at Wikipedia, but it isn't working correctly. So either I have misunderstood something or just done something wrong. Or most likely both...

Have a list of the first 500 primes which I use as a test and my implementation fails at number 40(or 41?).

Values differ at index [40] Expected: 179 But was: 175

Are you able to find my mistake, do you have an implementation laying around that you could share, or both?

The exact test I am using looks like this:

public abstract class AtkinTests
{
    [Test]
    public void GetEnumerator_FirstFiveHundredNumbers_AreCorrect()
    {
        var sequence = new Atkin(2000000);
        var actual = sequence.Take(500).ToArray();
        var expected = First500;

        CollectionAssert.AreEqual(expected, actual);
    }

    private static readonly ulong[] First500 = new ulong[]
        {
            2, 3, 5, 7, 11, 13, 17, ...
        };
}

This code:

for (ulong k = n*n; k <= limit; k *= k)
  isPrime[k] = false;

doesn't seem to be a faithful translation of this pseudocode:

is_prime(k) ← false, k ∈ {n², 2n², 3n², ..., limit}

Your code looks like it will run for n * n, n ^ 4, n ^ 8, etc. i.e. squaring each time instead of adding n-squared each time. Try this:

ulong nSquared = n * n;
for (ulong k = nSquared; k <= limit; k += nSquared)
  isPrime[k] = false;