Xác định nếu một số lượng nhất định là số nguyên tố trong Haskell

Question

Vì vậy, tôi đã nghĩ ra các chức năng sau đây cho thấy nếu một số lượng nhất định là số nguyên tố trong Haskell (nó giả định nguyên tố đầu tiên là 2):

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

nó có các lỗ hổng rõ ràng của việc tiếp tục đánh giá ngay cả khi nó có thể chia hết cho một số con số: (Có cách nào sane cách "cắt" đánh giá khi tìm thấy nhiều giải pháp, sử dụng tính năng hiểu danh sách?

Ngoài ra, Tôi sẽ không thực hiện các hoạt động khác ở đây, tôi chỉ đang cố gắng xem liệu có là những cách "khác lạ" hơn để làm điều tương tự.

Answer 1

Có lẽ không liên quan trực tiếp, nhưng về chủ đề tìm số nguyên tố bằng các ngôn ngữ chức năng tôi thấy sốcủa Melissa E. O'Neill rất thú vị.

Answer 2

Đây là nguồn lực tốt nhất cho prime numbers in haskell trong haskell.org

và đây prime.hs dự án github

Answer 3

Bỏ qua vấn đề số nguyên tố, và tập trung vào các điểm hẹp của một phương pháp hiệu quả hơn 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 

Answer 4

Thay đổi nhanh mã của bạn sẽ 'đoản mạch' việc đánh giá và dựa vào sự lười biếng của Danh sách Haskell là:

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

Ước tính đầu tiên của k sẽ khiến danh sách không trống và triển khai Haskell null sẽ chỉ xem xét phần tử đầu tiên của danh sách.

Bạn chỉ nên cần phải kiểm tra lên đến sqrt (k) tuy nhiên [1]:

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

Tất nhiên, nếu bạn đang tìm kiếm để làm thử nghiệm tính nguyên hiệu suất cao, thư viện được ưa thích.

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

Answer 5

Tôi thích cách tiếp cận này:

trước tiên hãy chức năng để có được tất cả các yếu tố của n:

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

Sau đó kiểm tra nếu các yếu tố chỉ số nhất định và 1, nếu có, số là số nguyên tố:

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