C#:阿特金的筛的实施 [英] C#: Implementation of the Sieve of Atkin
问题描述
我想知道是否有人在这里有一个很好的实现阿特金的筛的,他们想与大家分享。
我想实现它,但不能完全环绕它我的头。以下是我有这么远。</ P>
公共类阿特金: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;
这篇关于C#:阿特金的筛的实施的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!