0x49D1

0L4g0YDQsNC30YDQsNCx0L7RgtC60LUsINC00LvRjyDRgNCw0LfRgNCw0LHQvtGC0YfQuNC60L7QsiA=

Snippets: Решето Эратосфена


Для нахождения всех простых чисел не больше заданного числа n, следуя методу Эратосфена, нужно выполнить следующие шаги:
  • Выписать подряд все целые числа от двух до n (2, 3, 4, …, n).
  • Пусть переменная p изначально равна двум — первому простому числу.
  • Вычеркнуть из списка все числа от 2p до n, делящиеся на p (то есть, числа 2p, 3p, 4p, …)
  • Найти первое не вычеркнутое число, большее чем p, и присвоить значению переменной p это число.
  • Повторять шаги 3 и 4 до тех пор, пока p не станет больше, чем n
  • Все не вычеркнутые числа в списке — простые числа.
На практике, алгоритм можно немного улучшить следующим образом. На шаге №3, числа можно вычеркивать, начиная сразу с числа p2, потому что все составные числа меньше его уже будут вычеркнуты к этому времени. И, соответственно, останавливать алгоритм можно, когда p2 станет больше, чем n.
Можно показать, что сложность алгоритма составляет O(nloglogn) операций в модели вычислений RAM, или O(n(logn)(loglogn)) битовых операций.
Моя реализация (C#):
using System;
using System.Collections.Generic;

namespace EratosthenesSieve
{
    class Sieve
    {
        public List<Int32> GetPrimes(int n)
        {
            List<int> a = new List<int>();
            for (int i = 0; i < n; i++)
            {
                a.Add(i);
            }
            // 1 is not prime so :
            a[1] = 0;

            for (int s = 2; s < n; s++)
            {
                if (a[s] == 0) continue;

                for (int j = s * 2; j < n; j += s)
                {
                    a[j] = 0;
                }
            }
            a.RemoveAll(isZero);
            return a;
        }

        private bool isZero(int obj)
        {
            return obj == 0;
        }
    }
}

Тест:

Sieve s = new Sieve();
Stopwatch watch = new Stopwatch();

watch.Start();
Console.WriteLine(s.GetPrimes(1000000).Count);
watch.Stop();

Console.WriteLine("Elapsed: {0}", watch.Elapsed);
Console.WriteLine("In milliseconds: {0}", watch.ElapsedMilliseconds);
Console.WriteLine("In timer ticks: {0}", watch.ElapsedTicks);
Console.Read();


Результат:
78498 Elapsed: 00:00:00.1429397 In milliseconds: 142 In timer ticks: 409461 Intel Core 2 Duo E7500 @ 2.93GHz EratosthenesSieve.cs

Предлагайте лучшие реализации, ибо этот код-всего лишь базовая реализация алгоритма. Интересно послушать и про вариации.

Реклама

Добавить комментарий

Заполните поля или щелкните по значку, чтобы оставить свой комментарий:

Логотип WordPress.com

Для комментария используется ваша учётная запись WordPress.com. Выход / Изменить )

Фотография Twitter

Для комментария используется ваша учётная запись Twitter. Выход / Изменить )

Фотография Facebook

Для комментария используется ваша учётная запись Facebook. Выход / Изменить )

Google+ photo

Для комментария используется ваша учётная запись Google+. Выход / Изменить )

Connecting to %s

%d такие блоггеры, как: