Решето Эратосфена на C# с помощью LINQ


Может кто-то взглянуть на этот решето Эратосфена реализация? Это кажется почти слишком легко.

Вместо того, чтобы поддерживать отдельный бит[] для отслеживания ПРАЙМ/не Прайм, я просто извлекать noncandidates из коллекции полностью на каждой итерации.

Псевдокод

LIST = 2...n

set M = 1
while M < sqrt(n)
   set M = next number in LIST > M
   remove all multiples of M (excluding M itself) from LIST

В C#

int cur = 1, total = 1000;
var pc = Enumerable.Range(2, total).ToList();

while(cur <= Math.Sqrt(total))
{
    cur = pc.First(i => i > cur);
    pc.RemoveAll(i => i != cur && i % cur == 0);
}

Console.WriteLine(pc.Max());

Это кажется немного слишком легко. Результаты, кажется, верно. В Помощью Linqpad 4

  • Работает всего = 100000; в 0.008 сек
  • Работает всего = 1000000; в 0.141 сек
  • Работает всего = 10000000; в 2.973 сек


3944
8
задан 17 ноября 2011 в 11:11 Источник Поделиться
Комментарии
4 ответа

Да, это работает, но это медленно.

Я сравнил его с этого:

bool[] notPrime = new bool[total];
notPrime[0] = true;
notPrime[1] = true;
for (int i = 2; i <= Math.Sqrt(notPrime.Length); i++) {
if (!notPrime[i]) {
for (int j = i * 2; j < notPrime.Length; j += i) {
notPrime[j] = true;
}
}
}

перечисли.Ассортимент(2, Итого - 2) в коде LINQ, чтобы сделать его производят цифр от 2 до 99999, а не от 2 до 100001.)

Для итого = 100000, в среднем за 100 казней:

Linq 27.696966 ms., 0.280000 collections
Array 0.708616 ms., 0.030000 collections

Таким образом, это занимает много времени, а не сбор мусора.

10
ответ дан 17 ноября 2011 в 02:11 Источник Поделиться

обновление: как проверено и объяснено @Guffa и @EoinCampbell, это на самом деле гораздо медленнее.

Преимущества поиска HashSet , в основном, скорость доступа по индексу.
Поскольку алгоритм никогда не получает доступ к списку по индексу, поиска HashSet будет лишь вводить дополнительные накладные с хэширование и хранение внутренняя структура для быстрого доступа.


Я бы пользователей для поиска HashSet вместо списка.

Единственное изменение, которое нужно будет в это время .RemoveWhere() вместо .Метод removeall(): http://msdn.microsoft.com/en-us/library/bb361254.aspx

1
ответ дан 17 ноября 2011 в 01:11 Источник Поделиться

Вы обращаетесь модифицированные муфты в ваш операторами LINQ, так что я бы скопировать их на местных жителей.

        var cur = 1;
const int Total = 1000;
var pc = Enumerable.Range(2, Total).ToList();

while (cur <= Math.Sqrt(Total))
{
var cur1 = cur;
var cur2 = pc.First(i => i > cur1);

pc.RemoveAll(i => i != cur2 && i % cur2 == 0);
cur = cur2;
}

Console.WriteLine(pc.Max());

1
ответ дан 17 ноября 2011 в 03:11 Источник Поделиться

Я нашел ответ на переполнение стека несколько дней назад. Я его переделал немного, чтобы сделать его более параллельным и легче читать.

Я, возможно, ошибся. Я тестировал его на мой компьютер: процессор i7 второго поколения (3 ГГц) с 12 ГБ оперативной памяти.

Потребовалось несколько секунд, чтобы решить большинство из чисел меньше, чем 50,000,000. Однако, это заняло около 6:32 секунд, чтобы решить 100,000,000. Понадобилось всего 47 минут, чтобы решить 500,000,000. Он разбился через 11 часов после решения 1,5 миллиарда.

private static void GetPrimeNumbers(int max)
{
var allPossibleNumbers = Enumerable.Range(3, max-3);
var possiblePrime = allPossibleNumbers
.AsParallel()
.Where(n => Enumerable.Range(2, (int)Math.Sqrt(n))
.All(i => n % i != 0)
)
;
possiblePrime
.ToArray()
.AsParallel()
.Dump()
;
}

1
ответ дан 4 апреля 2013 в 02:04 Источник Поделиться