18

So I have devised the following function for seeing if a given number is a prime in Haskell (it assumes the first prime is 2):

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

it has the obvious pitfall of continuing the evaluation even if it is divisible by several numbers :(. Is there any sane way of "cutting" the evaluation when it finds more than one solution, using list comprehensions?

Also, which other implementations would you you try on? I'm not looking for performance here, I'm just trying to see if there are other more "haskellish" ways of doing the same thing.

Will Ness
  • 70,110
  • 9
  • 98
  • 181
devoured elysium
  • 101,373
  • 131
  • 340
  • 557
  • possible duplicate of [Lazy List of Prime Numbers](http://stackoverflow.com/questions/3596502/lazy-list-of-prime-numbers) – Landei Jan 14 '11 at 12:37

6 Answers6

33

A quick change to your code that will 'short circuit' the evaluation, and relies on the laziness of Haskell Lists, is:

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

The very first divisor of k will cause the list to be non-empty, and the Haskell implementation of null will only look at the first element of the list.

You should only need to check up to sqrt(k) however:

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

Of course, if you are looking to do high-performance primality testing, a library is preferred.

Rouli Freman
  • 315
  • 3
  • 10
tildedave
  • 679
  • 5
  • 8
  • @Can your edit had broken this post. please don't do that. – Will Ness Jul 26 '19 at 20:38
  • @JamesKPolk thank you for rejecting a nonsensical edit on this post. :) – Will Ness Jul 26 '19 at 20:45
  • @WillNess I re-checked my edit. Yet again I don't see how it deviates from the original answer. All of the information from the original author is preserved. As my edit note stated, it was just a minor formatting edit that fixed some wordings and styling. – Can Jul 27 '19 at 08:47
  • @WillNess It could be nonsensical to you but it wasn't for me, and certainly not for others as well since it also got approved by two others. All of the time, I edit posts on SE to make them more readable and approachable; and they get approved. These changes I've made could seem pointless to you but they're important indeed. Learning is crucial and information should be presented as best as it could. – Can Jul 27 '19 at 08:49
  • @Can "yet again" (? it's our first communication that I know of.) two things you broke: 1. you changed `isqrt` to `sqrt` which doesn't work with Integral types, so the code would cause an error. 2. you changed "relies" to "rely" which broke the meaning of the sentence (in a bit subtle, but still real, sense). – Will Ness Jul 27 '19 at 08:50
  • @WillNess Anyway, I don't care if you've reverted my edit. However, as a last statement, I would like to say that calling something that others have also supported nonsensical is both weird and more importantly rude. Make it a habit to first ask why. – Can Jul 27 '19 at 08:50
  • @Can it is an unfortunate fact that your edit broke the post in two ways which I showed to you above, after you've asked. It is good to engage in a dialog, to clear things up. You shouldn't take personally the critique of an artifact, even if produced by you. See https://www.dreamsongs.com/10ideas.html for more about that. – Will Ness Jul 27 '19 at 08:52
  • @WillNess rest assured, I'm definitely not taking it personally but just stating what I think. True, changing `isqrt` to `sqrt`(hey, learned something new, thank you) was a mistake and I missed the word `rely` when I was typing fast but those weren't the only changes. Anyway, I really don't want to take this further. Thanks. – Can Jul 27 '19 at 08:59
  • @Can happy trails! – Will Ness Jul 27 '19 at 09:00
  • See https://stackoverflow.com/a/6695714/839733 for a definition of `isqrt`, which is missing in the answer. – Abhijit Sarkar Dec 31 '22 at 09:03
12

Here is the best resource for prime numbers in haskell in haskell.org

and here prime.hs github project

8

I like this approach:

First make function to get all factors of n:

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

Then check if factors are only the given number and 1, if so, the number is prime:

prime n = factors n == [1,n]
notgiorgi
  • 1,691
  • 12
  • 27
7

It's perhaps not directly relevant, but on the topic of finding primes in functional languages I found Melissa E. O'Neill's The Genuine Sieve of Eratosthenes very interesting.

gspr
  • 11,144
  • 3
  • 41
  • 74
4

Ignoring the primes issue, and focusing on the narrow point of a more efficient method of 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
dave4420
  • 46,404
  • 6
  • 118
  • 152
0

This may be silly and inefficient (I'm a complete Haskell newby), but the function isMyNumberPrime (in ghci) seems to tell you if a number is prime or not.

factors n = [x | x <- [2..(n`div` 2)], mod n x == 0]
factormap n = fmap factors $ factors n
isMyNumberPrime n = case factormap n of [] -> True; _ -> False
DMJ
  • 41
  • 3
  • For a complete Haskell newbie not so bad. I tested it for some small numbers, and it worked. However, how does this work, anyway? Which factors does `factors` provide? It doesn't seem to be prime factors, nor all the factors. For instance the prime factors of `8` are `[2,2,2]` and the factors are `[1, 2, 4, 8]` - but your function provides something different. The next question is why `map` - factors of factors? Please, if you don't mind than I would edit your post or please explain better. Thank you. – Jörg Brüggmann Apr 23 '22 at 14:10
  • Factors can be evaluated by `factors n = [ n' | n' <- [1..n], n \`mod\` n' == 0]` – Jörg Brüggmann Apr 23 '22 at 14:12
  • Primes are numbers that just have 1 and the prime as factors and hence `isPrime n = factors n == [1,n]`. – Jörg Brüggmann Apr 23 '22 at 14:29
  • The code `factors n = [x | x <- [2..(n\`div\` 2)], mod n x == 0]`, and `factormap n = fmap factors $ factors n`, `isMyNumberPrime n = case factormap n of [] -> True; _ -> False` does not work for `1`. One is not a prime number, and `isMyNumberPrime 1` evaluates `True`. – Jörg Brüggmann Apr 23 '22 at 14:35
  • Thank you for your comment, Jorg. Unfortunately, it was so long ago that I posted the function that I've totally forgotten how it works (and much of Haskell, for that matter) – DMJ Apr 24 '22 at 21:05