Инициализировать решето Эратосфена в Scala


Я учусь Скала, решая некоторые упражнения, и я в настоящее время решения упражнений, где мне нужно инициализировать решето Эратосфена.

Я использую следующий код:

  val sieve = Array.fill[Boolean](100)(true)

  for (p <- 2 until sieve.length if sieve(p) && math.pow(p, 2) <= sieve.length) {
    for (i <- p * 2 until sieve.length by p) {
      sieve(i) = false
    }
  }

Я вижу некоторые проблемы с этим подходом, например, внешний цикл по-прежнему оценивает все числа от некоторых г до сито.длина для проверки состояния решета(Р) && математика.пр(п,2) <= решето.длина, хотя код внутри цикла не выполняется для тех значений Р.

Я думаю, что это может быть решена с помощью следующего кода:

 var p = 2
 while(math.pow(p, 2) <= sieve.length)
 {
   if(sieve(p))
     for (i <- p * 2 until sieve.length by p)
       sieve(i) = false

   p += 1
 }

Возможно, я ошибаюсь, но я думаю, что я осложняющих слишком много.

Что это хороший способ, чтобы инициализировать решето Эратосфена в Scala?



493
3
задан 3 августа 2011 в 10:08 Источник Поделиться
Комментарии
1 ответ

Есть много других способов писать решето Эратосфена в Scala. Что касается этой конкретной код, для понимания лучше записать так:

val sieve = Array.fill[Boolean](100)(true)

for {
p <- 2 until sieve.length
if sieve(p) && math.pow(p, 2) <= sieve.length
i <- p * 2 until sieve.length by p
} sieve(i) = false

Кроме того,


внешний цикл по-прежнему оценивает все числа от некоторых гдо
решето.длина для проверки состояния решета(Р) && математика.пр(п,2) <=
решето.длина
,

Ты тоже можешь вычислить квадратный корень, хотя это дорогостоящее вычисление. Вы можете использовать takeWhile , чтобы избежать его:

p <- 2 until sieve.length takeWhile (x => x * x < sieve.length)

Кроме того, место на последнем круге может быть улучшена:

i <- p * p until sieve.length by p

В целом, вы получите это:

val sieve = Array.fill[Boolean](100)(true)

for {
p <- 2 until sieve.length takeWhile (x => x * x < sieve.length)
if sieve(p)
i <- p * p until sieve.length by p
} sieve(i) = false

Теперь, я бы не стал использовать переключатели для этого, ни выбора. Вместо этого, я предпочитаю реализации (эффективности) использования BitSet вместо. Например:

val last = 100
val numbers = 2 to last
val sieve = collection.mutable.BitSet(numbers: _*)
for (p <- numbers takeWhile (x => x * x <= last) if sieve(p))
sieve --= p * p to last by p

Есть и другие реализации я ценю за их функциональный характер, но я оставлю это другим.

6
ответ дан 4 августа 2011 в 12:08 Источник Поделиться