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

Question

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

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

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

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

Answer 1

Быстрое изменение в вашем коде, которое «закоротит» оценку и полагается на лень списков Haskell:

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

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

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

isPrime k = null [ x | x <- [2..isqrt k], k `mod` x == 0]

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

[1] http://www.codecodex.com/wiki/Calculate_an_integer_square_root#Haskell

Answer 2

Вот лучший ресурс для простых чисел в haskell в haskell.org

и здесь prime.hs github project

Answer 3

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

Answer 4

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

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

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

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

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

Answer 5

Игнорирование вопроса о простых числах и сосредоточение на узкой точке более эффективного метода 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