Быстрый алгоритм поиска простых чисел? [дубликат]

На этот вопрос уже есть ответы здесь :

Какой алгоритм является самым быстрым для поиска простых чисел? (14 ответов)

Закрыт 6 лет назад .

Прежде всего - я много проверял на этом форуме и не нашел ничего достаточно быстро . Я пытаюсь создать функцию, которая возвращает мне простые числа в указанном диапазоне. Например, я выполнил эту функцию (на C #) с помощью сита Эратосфена. Я пробовал также сито Аткина, но сито Эратосфена работает быстрее (в моей реализации):

public static void SetPrimesSieve(int Range)
    {
        Primes = new List();
        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);
    }

Оно работает примерно в два раза быстрее, чем коды и алгоритмы, которые я нашел ... Должен быть более быстрый способ поиска простых чисел, не могли бы вы мне помочь?

задан starblue 28 October 2010 в 19:08

0 ответов

Другие вопросы по тегам:

algorithm performance primes sieve-of-eratosthenes

Быстрый алгоритм поиска простых чисел? [дубликат]

0 ответов

Похожие вопросы: