C#: реализация решета Atkin
Существует другая причина, почему стиль кода важен. Это может действовать как прокси для определения профессионализма программиста. Так же, как растушевки хвоста павлина демонстрируют его здоровье, и мужество (нездоровый организм не был бы в состоянии посвятить дефицитные ресурсы в создание шикарного хвоста), стиль программы может показать много относительно человека, который записал его.
, Когда я вижу плохо отформатированный код с непоследовательными соглашениями о присвоении имен и недостаточными комментариями, я держусь далеко от него не только потому, что такой код по сути нечитабелен, но также и потому что код, довольно вероятно, будет питать еще худшие проблемы под этой неприятной поверхностью.
2 ответа
Этот код:
for (ulong k = n*n; k <= limit; k *= k)
isPrime[k] = false;
, похоже, не является точным переводом этого псевдокода:
is_prime(k) ← false, k ∈ {n², 2n², 3n², ..., limit}
Ваш код выглядит так, как будто он будет работать для n * n, n ^ 4, n ^ 8 и т. Д. Т.е. возведение в квадрат каждый раз вместо добавления n-квадрата каждый раз. Попробуйте следующее:
ulong nSquared = n * n;
for (ulong k = nSquared; k <= limit; k += nSquared)
isPrime[k] = false;
Вот Другая реализация. Он использует BitArray для сохранения памяти. Параллель .NET Framework 4.
static List<int> FindPrimesBySieveOfAtkins(int max)
{
// var isPrime = new BitArray((int)max+1, false);
// Can't use BitArray because of threading issues.
var isPrime = new bool[max + 1];
var sqrt = (int)Math.Sqrt(max);
Parallel.For(1, sqrt, x =>
{
var xx = x * x;
for (int y = 1; y <= sqrt; y++)
{
var yy = y * y;
var n = 4 * xx + yy;
if (n <= max && (n % 12 == 1 || n % 12 == 5))
isPrime[n] ^= true;
n = 3 * xx + yy;
if (n <= max && n % 12 == 7)
isPrime[n] ^= true;
n = 3 * xx - yy;
if (x > y && n <= max && n % 12 == 11)
isPrime[n] ^= true;
}
});
var primes = new List<int>() { 2, 3 };
for (int n = 5; n <= sqrt; n++)
{
if (isPrime[n])
{
primes.Add(n);
int nn = n * n;
for (int k = nn; k <= max; k += nn)
isPrime[k] = false;
}
}
for (int n = sqrt + 1; n <= max; n++)
if (isPrime[n])
primes.Add(n);
return primes;
}