J (Тацит) Сито Эратосфена

Я ищу код J, чтобы сделать следующее.

Предположим, у меня есть список случайных целых чисел (отсортированных), 2 3 4 5 7 21 45 49 61. Я хочу начать с первого элемента и удалить все кратные элементу в списке, а затем перейти к следующему элементу, отменить его кратные , так далее и так далее.

Таким образом, результат, на который я смотрю, равен 2 3 5 7 61. По сути, это сито Эратосфена. Был бы признателен, если бы кто-нибудь мог объяснить код, так как я изучаю J и мне трудно получить большинство кодов :(

С уважением, бабсдок


primes sieve-of-eratosthenes j
person babsdoc    schedule 28.11.2012    source источник

Ответы (2)


arrow_upward
4
arrow_downward

Это не совсем то, о чем вы спрашиваете, но вот более идиоматическая (и гораздо более быстрая) версия Sieve.

По сути, вам нужно проверить, какое число является кратным. Вы можете получить это из таблицы модулей: |/~

l =: 2 3 4 5 7 21 45 49 61
|/~ l
  0 1 0 1 1  1  1  1  1
  2 0 1 2 1  0  0  1  1
  2 3 0 1 3  1  1  1  1
  2 3 4 0 2  1  0  4  1
  2 3 4 5 0  0  3  0  5
  2 3 4 5 7  0  3  7 19
  2 3 4 5 7 21  0  4 16
  2 3 4 5 7 21 45  0 12
  2 3 4 5 7 21 45 49  0

Каждая пара кратных дает 0 на столе. Теперь нас не интересуют 0, соответствующие собственным модулям (2 по модулю 2, 3 по модулю 3 и т. д.; 0 по диагонали), поэтому мы должны их удалить. Один из способов сделать это — добавить вместо них 1, например:

=/~ l
  1 0 0 0 0 0 0 0 0
  0 1 0 0 0 0 0 0 0
  0 0 1 0 0 0 0 0 0
  0 0 0 1 0 0 0 0 0
  0 0 0 0 1 0 0 0 0
  0 0 0 0 0 1 0 0 0
  0 0 0 0 0 0 1 0 0
  0 0 0 0 0 0 0 1 0
  0 0 0 0 0 0 0 0 1
(=/~l) + (|/~l)
  1 1 0 1 1  1  1  1  1
  2 1 1 2 1  0  0  1  1
  2 3 1 1 3  1  1  1  1
  2 3 4 1 2  1  0  4  1
  2 3 4 5 1  0  3  0  5
  2 3 4 5 7  1  3  7 19
  2 3 4 5 7 21  1  4 16
  2 3 4 5 7 21 45  1 12
  2 3 4 5 7 21 45 49  1

Это также может быть записано как (=/~ + |/~) l.

Из этой таблицы мы получаем окончательный список чисел: каждое число, столбец которого содержит 0, исключается.

Мы строим этот список исключений, просто умножая его на столбец. Если столбец содержит 0, его произведение равно 0, в противном случае это положительное число:

*/ (=/~ + |/~) l
   256 2187 0 6250 14406 0 0 0 18240

Прежде чем сделать последний шаг, нам нужно немного улучшить это. Нет причин выполнять длинные умножения, так как нас интересуют только 0s и not-0s. Итак, при построении таблицы мы сохраним только 0s и 1s, взяв "знак" каждого числа (это signum:*):

* (=/~ + |/~) l
  1 1 0 1 1 1 1 1 1
  1 1 1 1 1 0 0 1 1
  1 1 1 1 1 1 1 1 1
  1 1 1 1 1 1 0 1 1
  1 1 1 1 1 0 1 0 1
  1 1 1 1 1 1 1 1 1
  1 1 1 1 1 1 1 1 1
  1 1 1 1 1 1 1 1 1
  1 1 1 1 1 1 1 1 1

so,

*/ * (=/~ + |/~) l
  1 1 0 1 1 0 0 0 1

Из списка исключений вы просто добавляете copy:# числа в свой окончательный список:

l #~ */ * (=/~ + |/~) l
   2 3 5 7 61

or,

(]#~[:*/[:*=/~+|/~) l
   2 3 5 7 61
person Eelvex    schedule 29.11.2012
comment
Я согласен, что это более естественный подход в J, и я думаю, что особенно важно научиться отдавать предпочтение методам всего массива. - person kaleidic; 29.11.2012
comment
Спасибо. И Eelvex, и Kaleidic, я собираюсь попробовать оба этих решения и импровизировать, это определенно выглядит для меня хорошей отправной точкой. Объяснения, которые вы оба дали, также очень хороши и подробны, спасибо, что нашли время. Очень признателен. Хорошего дня :) - person babsdoc; 01.12.2012

arrow_upward
2
arrow_downward

Неявная итерация обычно выполняется с помощью союза Power. Когда тест на завершение должен быть чем-то другим, кроме достижения точки фиксации, Do While конструкция работает хорошо.

В этом решении filterMultiplesOfHead применяется повторно, пока не останется неиспользованных или отфильтрованных чисел. Уже примененные числа накапливаются в частичном ответе. Когда список для обработки пуст, частичный ответ является результатом после снятия бокса, используемого для отделения обработанных данных от необработанных.

   filterMultiplesOfHead=: {. (((~: >.)@ %~) # ]) }.
   appendHead=: (>@[ , {.@>@])/
   pass=: appendHead ; filterMultiplesOfHead@>@{:
   prep=: a: , <
   unfinished=: [: -. a: -: {:
   sieve=: [: ; [: pass^:unfinished^:_ prep

   sieve 2 3 4 5 7 21 45 49 61 
2 3 5 7 61

   prep 2 3 4 7 9 10
┌┬────────────┐
││2 3 4 7 9 10│
└┴────────────┘
   appendHead prep 2 3 4 7 9 10
2
   filterMultiplesOfHead 2 3 4 7 9 10
3 7 9
   pass^:2 prep 2 3 4 7 9 10
┌───┬─┐
│2 3│7│
└───┴─┘
   sieve 1-.~/:~~.>:?.$~100
2 3 7 11 29 31 41 53 67 73 83 95 97
person kaleidic    schedule 28.11.2012
comment
Я делаю sieve 1-.~/:~~.>:?$~100 и получаю несколько множителей, которых не должен. Я не понимаю, почему... - person Eelvex; 29.11.2012
comment
То, что я опубликовал изначально, отфильтровывало только простые множители, что было неверно. Я изменил это, чтобы отфильтровать каждое число, для которого рассматриваемое число является фактором. Спасибо, что предупредили меня о проблеме - person kaleidic; 29.11.2012