Определение того, является ли данное число простым в haskell

Поэтому я разработал следующую функцию для определения, является ли данное число простым числом в Haskell (предполагается, что первое простое число равно 2):

isPrime k = length [ x | x <- [2..k], k 'mod' x == 0] == 1

он имеет очевидную ловушку продолжения оценки, даже если она делится на несколько чисел :(. Есть ли какой-то вменяемый способ "вырезать" оценку, когда она находит более одного решения, используя списочные выражения?

Кроме того, какие еще реализации вы бы примерили? Я не ищу здесь производительность, я просто пытаюсь понять, есть ли другие, более "скромные" способы сделать то же самое.

Ответы

Ответ 1

Быстрое изменение в вашем коде, которое "закоротит" оценку и будет опираться на ленивость списков Хаскелла:

isPrime k = if k > 1 then null [ x | x <- [2..k - 1], k 'mod' x == 0] else False

Самый первый делитель k приведет к тому, что список будет не пустым, а реализация null на Haskell будет рассматривать только первый элемент списка.

Вам нужно только проверить до sqrt(k) однако:

isPrime k = if k > 1 then null [ x | x <- [2..isqrt k], k 'mod' x == 0] else False

Конечно, если вы хотите провести высокопроизводительное тестирование на простоту, предпочтительнее использовать библиотеку.

Ответ 3

Возможно, это не имеет непосредственного отношения, но на тему поиска простых чисел в функциональных языках я нашел Мелиссу Э. О'Нил Подлинным ситом Эратосфена очень интересной.

Ответ 4

Игнорирование проблемы с пробелами и фокусировка на узкой точке более эффективного метода length xs == n:

hasLength :: Integral count => [a] -> count -> Bool
_        `hasLength` n | n < 0 = False
[]       `hasLength` n         = n == 0
(_ : xs) `hasLength` n         = xs `hasLength` (pred n)

isPrime k = [ x | x <- [2..k], k `mod` x == 0)] `hasLength` 1

Ответ 5

Мне нравится этот подход:

Сначала сделайте функцию, чтобы получить все факторы n:

factors n = [x | x <- [1..n], mod n x == 0]

Затем проверьте, являются ли коэффициенты только заданным числом и 1, если это так, число является простым:

prime n = factors n == [1,n]