Реализация isPrime в Scala с использованием хвостовой рекурсии - PullRequest
Новая
       11

Реализация isPrime в Scala с использованием хвостовой рекурсии

0 голосов
/ 08 января 2019

Я работаю над упражнением, которое требует от меня реализации isPrime в scala с использованием хвостовой рекурсии. Однако у меня есть реализация, у меня проблемы с созданием правильного базового варианта.

Так что мой алгоритм включает проверку всех чисел от 2 до N / 2, так как N / 2 будет наибольшим фактором N. 

def isPrime(n: Int): Boolean = {
    def isPrimeUntil(t: Int): Boolean = {
        if(t == 2) true
        else n % t != 0 && isPrimeUntil(t - 1)
    }

    isPrimeUntil(n/2)
}

Поэтому, если я хочу проверить, является ли 15 простым, я проверю все числа от 7 до 2.

Вот мой след:

isPrimeUntil(7) -> true && isPrimeUntil(6) -> true && isPrimeUntil(5) -> false && isPrimeUntil(4)

Из-за оценки короткого замыкания функция возвращает false в этот момент.

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

Ответы [ 2 ]

0 голосов
/ 08 января 2019

3 не единственная ваша проблема. Он также возвращает true для 4 ... Ваш базовый случай должен быть 1, а не 2: 

   def isPrimeUntil(t: Int): Boolean = t == 1 || t > 1 && n%t != 0 && isPrimeUntil(t-1)
0 голосов
/ 08 января 2019

Хотя Кшистоф правильно указал, что источником проблемы является целочисленное деление, мне не нравится его решение. Я считаю, что правильным решением является изменение теста на 

 if(t <= 2) true

С такой проверкой в ​​случае n = 3 и, таким образом, n/2 = 1 он остановится, не перейдя к t = 0.

Некоторые преимущества:

  • Модифицированная проверка (t <= 2) практически на любом современном оборудовании так же эффективна, как проверка для (t == 2)
  • ИМХО это лучше передает логику
  • Это очень неэффективный способ написать (n.toDouble/2).ceil.toInt таким образом. Писать (n+1)/2 проще и быстрее, чем делать 2 преобразования (в удвоение и обратно в int)
  • Не требует чрезмерной проверки всех нечетных n ((n+1)/2 никогда не является наименьшим делителем для нечетных n, где существует разница между n/2 и ceil(n/2))
...