7
Po pierwsze - dużo sprawdziłem na tym forum i nie znalazłem wystarczająco szybko wystarczająco szybko. Próbuję utworzyć funkcję, która zwróci mi liczby pierwsze w określonym zakresie. Na przykład zrobiłem tę funkcję (w języku C#) za pomocą sita Eratostenesa. Próbowałem też sito Atkin, ale jeden Eratosthenes działa szybciej (w moim realizacji):Szybki algorytm wyszukiwania liczb pierwszych?
public static void SetPrimesSieve(int Range)
{
Primes = new List<uint>();
Primes.Add(2);
int Half = (Range - 1) >> 1;
BitArray Nums = new BitArray(Half, false);
int Sqrt = (int)Math.Sqrt(Range);
for (int i = 3, j; i <= Sqrt;)
{
for (j = ((i * i) >> 1) - 1; j < Half; j += i)
Nums[j] = true;
do
i += 2;
while (i <= Sqrt && Nums[(i >> 1) - 1]);
}
for (int i = 0; i < Half; ++i)
if (!Nums[i])
Primes.Add((uint)(i << 1) + 3);
}
Biegnie około dwa razy szybciej niż kody & algorytmów znalazłem ... Tam powinien być szybszy sposób na znalezienie liczb pierwszych, czy mógłbyś mi pomóc?
In w jakim zakresie szukasz liczb pierwszych? Tylko od 0 do maks. Int? Jak szeroki jest zasięg? – Gleno
Załóżmy, że coś podobnego do miliarda/2 – Ohad
Istnieje 50M liczb pierwszych mniejszych niż 10^9, więc ich wstępne obliczenia dałyby tabelę o wielkości 200 MB. W rzeczywistości przechowywanie sita byłoby mniejsze (10^9 bitów to 125MB, a ty nie musisz przechowywać bitów parzystych, abyś mógł zmieścić to wszystko poniżej 64 MB). – Gabe