Гроздь и Малахид: Сито Эратосфена

Я взял немного от всех ответов на мой предыдущий вопрос Обмолот: сито Эратосфена .


Это может быть граничащим с кодовым гольф-играми, но я думаю, что у меня здесь довольно хороший кусок кода.

Есть ли какие-то основные концепции, которые я пропускаю, хотя все еще кажется очень простым?

var upperLimit = 9999;
var primes = new List<long>();
primes.Add(1);
primes.Add(2);
for (var i = 3; i < upperLimit; i+=2)
{
    primes.Add(i);
}

for (var i = 7; i < upperLimit; i+=2)
{
    foreach (var number in primes.ToList())
    {
        if (number == i) { continue; }
        if (number % i == 0) { primes.Remove(number); }
    }
}
primes.ForEach(Console.WriteLine);
Console.WriteLine("The Last Prime is " + primes[primes.Count - 1]);
Console.WriteLine("what are you waiting for? Exit the program!");

Очевидно, я мог бы начать со всех простых чисел, которые я знаю, просто добавив их, чтобы начать, а затем начал мои циклы выше, но я думаю, что это немного обманывает.

Есть ли способ сделать это быстрее и способен вычислять (и хранить) более высокие номера, используя меньше памяти?

11 голосов | спросил Malachi 10 J000000Thursday14 2014, 00:19:04

4 ответа


8

Первая проблема: 1 не является простым числом.

Вторая проблема после фиксации:

Console.WriteLine(string.Join(", ", primes.Take(10)));
  

2, 3, 5, 7, 9 , 11, 13, 15 , 17, 19

Третья проблема: это не сито Эратосфена. Чтобы процитировать Википедию (внимание мое):

  
  1. Создайте список последовательных целых чисел из \ $ 2 \ $ через \ $ n \ $: \ $ (2, 3, 4, \ ldots, n) \ $.

  2.   
  3. Изначально пусть \ $ p \ $ равно $ 2 \ $, первое простое число.

  4.   
  5. Начиная с \ $ p \ $, перечислите его кратность путем подсчета до \ $ n \ $ с приращениями \ $ p \ $,   и пометьте их в списке (это будут $ 2p \ $, \ $ 3p \ $, \ $ 4p \ $ и т. д., \ $ p \ $   сам не должен быть помечен).

  6.   
  7. Найдите первое число, большее, чем \ $ p \ $   в списке, который не отмечен. Если такого номера не было, остановитесь.    В противном случае пусть \ $ p \ $ теперь будет равным этому новому числу (что является следующим   prime) и повторите шаг 3 .

  8.   
ответил mjolka 10 J000000Thursday14 2014, 09:17:54
10

Эта строка ужасна, ужасна и несчастна:

if (number % i == 0) { primes.Remove(number); }

Эта строка в основном (за кадром) делает следующее:

  • сканировать все данные с самого начала, пока вы не найдете элемент со значением number
  • , если вы найдете это значение:
    • для каждого оставшегося значения, сдвиньте его назад (замените каждый n значением на n + 1).
    • уменьшить размер списка на 1.

Вышеуказанная операция \ $ O (n) \ $.

Использование индексированного метода для удаления значения будет намного быстрее, и структура данных, такая как Linked list с \ $ O (1) \ $ remove, будет иметь огромное значение.

ответил rolfl 10 J000000Thursday14 2014, 04:20:22
5

List<T>, вероятно, не самая быстрая структура данных. Связанный список на самом деле был бы идеальным здесь. Каждый элемент отслеживает пробел после него.

Node head = new Node(1);
Node current = head.next = new Node(2);
current = current.next = new Node(3);

Тогда это будет пропускать кратные 2 и 3. Вы могли бы принять его, если хотите.

for (var i = 7; i < upperLimit; i+=6)
{
    current = current.next = new Node(i-2);
    current = current.next = new Node(i);
}
if (i-2 < upperLimit)
  current.next = new Node(i-2); //bounds correction

Затем вы можете уменьшить количество i, которое вы используете, просто перейдя к следующему шагу вместо i + = 2. Это то, что делает реальное сито и является большим замедлением для вашего кода.

current = head.next.next; //this will get 3, since we have no factors of 1,2,3. So the loop will start at 5.
while((current = current.next) != null)
{
  int num = current.data;
  Node current2 = current;
  while((current2 = current2.next) != null)
  {
    if (current2.data % num == 0)
    {
      current2.next = current2.next.next;
    }
  }
}

После этого все узлы являются порядковыми числами. Вы также можете переместить их в массив с одной итерацией связанного списка.

ответил Jean-Bernard Pellerin 10 J000000Thursday14 2014, 03:28:58
4

Чтобы сделать это очень быстро, просто используйте массив логических элементов, где True означает, что индекс index является простым.

[0] False

[1] False

[2] True

[3] True

[4] False

...

Когда вы будете готовы распечатать простые числа, просто перейдите по массиву.

Изменить: Поскольку неясно, что я имею в виду, вот пример кода.

 int n = SOME_VALUE_HERE;
 int N = n*n;
 boolean[] isPrime = new boolean[N];

 Arrays.fill(isPrime, true);
 isPrime[0] = false; isPrime[1] = false;
 for (int i = 2; i < N; i++)
     if (isPrime[i]) 
         for (int j = 2*i; j < N; j+=i)
             isPrime[j] = false;

Все оставшиеся истинные значения - это простые числа.

ответил Syd Kerckhove 10 J000000Thursday14 2014, 14:01:25

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

Популярные теги

security × 330linux × 316macos × 2827 × 268performance × 244command-line × 241sql-server × 235joomla-3.x × 222java × 189c++ × 186windows × 180cisco × 168bash × 158c# × 142gmail × 139arduino-uno × 139javascript × 134ssh × 133seo × 132mysql × 132