CODEWITHSUNDEEP
haskellprimes
Vitim.us
Vitim.us

Reputation: 22128

Recursive function to find if a number is prime or not

I need to implement a recursive function that returns 1 if the number is prime or 0 otherwise. The homework problem says that I can't use '%' mod. Haskell should be something like this... I'm not sure.

isprime x = prime(x sqrt(x))

prime x i = | i==1 = 1
            | mod(x i)==0 = 0
            | otherwise = prime(x i-1)

mod num div | num<div = n
            | otherwise = mod(num-div div)

I tested an algorithm in C because I don't have a Haskell compiler on my Mac, but there's something wrong because it's returning false positive on primes-1. idk why.

int main (int argc, const char * argv[]){
    int a=0,b=31;
    printf("\n Prime numbers between %d and %d \n",a,b);

    for(int a=0; a<=b; a++){
        if(isPrime(a)==0){
            printf("%d, ",a);
        } 
    }
    return 0;
}

int isPrime(int x){
    return prime(x, sqrt(x));
}

int prime(int x, int i){
    if(i==0){
        return 0;
    }
    else if(mod(x,i)==1){
        return 1;
    }
    else{
        return prime(x, i-1);
    }
}

int mod(int num, int div){
    if(num<div) return num;
    else return mod(num-div, div);
}

The algorithm is returning this:

Prime numbers between 0 and 31 
0, 1, 2, 3, 4, 6, 8, 12, 14, 18, 20, 24, 30,
Program ended with exit code: 0

Upvotes: 1

Views: 5052

Answers (3)

Will Ness
Will Ness

Reputation: 71070

(apparently, there's a new policy regarding homework, viz. "If you don't want a fully vetted, complete and testable answer, Stack Overflow is not the place to ask - by Tim Post", so here goes).

Basically, your code is almost correct (1 is not a prime), sans some syntax issues. 

isprime x = prime x (floor $ sqrt $ fromIntegral x)   where
  prime x i | i==1 && x > 1  = 1
            | x == i*div x i = 0
            | otherwise      = prime x (i-1)

-- mod x i = x - i*div x i
-- mod x i == 0 = x == i*div x i

fromIntegral is just some adaptor which lets us use an Integral value as an argument to sqrt which expects a Floating argument. Try using :i sqrt or :i Integral etc. at the GHCi prompt (also read some documentation google around).

But algorithmically there's place for improvement. First of all, it's much better to try out the divisors in the other direction, from 2 up to the number's sqrt, because any given number is more likely to have a smaller factor than a larger one. Second, after trying out 2, there's no need to try out any other even number as a possible divisor. This gives us

isprime x | x == 2          = 1
          | x < 2 || even x = 0
          | otherwise       = go 3
  where
    r = floor $ sqrt $ fromIntegral x
    go i | i > r          = 1
         | x == i*div x i = 0        -- really, | rem x i == 0 = 0
         | otherwise      = go (i+2)

This would normally be written down using Bools, and a higher-order function like and which captures the recursions and testing pattern (so it is not recursive anymore):

isprime x = if isPrime x then 1 else 0

isPrime x = x==2 || x>2 && odd x && 
              and [rem x d /= 0 | d <- [3,5..floor $ sqrt $ fromIntegral x]]

There's some redundancy in there still: after we've tested by 3, there's no need to test by any of its multiples too (just like we did with 2 and evens). We really just need to test by prime factors:

isPrime x = x>1 && and 
    [rem x d /= 0 | d <- takeWhile (<= (floor $ sqrt $ fromIntegral x)) primes]

primes = filter isPrime [2..]
       = 2 : filter isPrime ([3..] `minus` [4,6..])
       = 2 : filter isPrime [3,5..]
       = 2 : 3 : filter isPrime ([5,7..] `minus` [9,15..])
       = 2 : 3 : 5 : filter isPrime (([7,9..]`minus`[9,15..])`minus`[25,35..])
       ...........

Here we see the emergence of the sieve of Eratosthenes, P = {3,5, ...} \ U {{p2, p2 + 2p, ...} | p in P} (w/out the 2).

see also:

Upvotes: 1

AndrewC
AndrewC

Reputation: 32455

Your basic idea is fine. In Haskell you can use lists instead of iteration. Here's what you need to look into:

  1. Install and play with ghci.
  2. If you have no idea how to do anything in Haskell, visit Learn You a Haskell for Great Good http://learnyouahaskell.com/
  3. List comprehensions. Lean what [n^2 | n <- [1..10]] means and play with similar lists.
  4. Look up functions like sqrt on hoogle http://www.haskell.org/hoogle/
  5. Because Haskell is statically typed you will need to convert some numerical types between Integer and Float. Look up Float -> Integer and Integer -> Float when you do. DON'T use unsafeCoerce - it's unsafe and will break things badly.
  6. Use hoogle to look up [Bool] -> Bool. Why did I suggest that? How would [Bool] help, and how would you make one anyway? (Revise list comprehension again.)
  7. Come back with more specific questions once you've found out more and had a go.
  8. Always start your assignments early, especially if you've missed classes!

You were set this homework not because the department was stuck for a way of deciding whether 102659473841923461 is prime, but because they want you to learn some Haskell. Try not to try to solve the problem without doing the learning - it'll only make the next assignment even harder! (This is why I've resisted the temptation to translate the "pseudocode" in another answer into Haskell.)

Upvotes: 5

alanmanderson
alanmanderson

Reputation: 8200

I don't know Haskell, and I don't want to hand you the answer, but I can offer a method.

if you check all the numbers from 2 to sqrt(n), and none of them are factors of n, then n is prime.

So maybe a function call with the following pseudo code might work:

def isPrime(n):
   return isPrimeHelper(n,sqrt(n))

def isPrimeHelper(n,counter):
   if counter == 1 return True
   if n % counter == 0 return False
   else return isPrime(n,counter-1)

Upvotes: 1

Related Questions