Haskell code: how to skip every other number in a list of primes-CodePudding

The objective is to get a list of primes that skips every other prime number. An example would be primeskip 10 --> [2,5,11,17,23,31,41,47,59,67]. I am pretty sure my prime function works but I am doing something wrong in the skip.

This is the code that I have.

isPrime n = ip n [2..(n `div` 2)]
    where
    ip _ [] = True
    ip n (x:xs)
        | n `mod` x == 0 = False
        | otherwise = ip n xs

primeskip :: Int -> [Int]
primeskip n = take n [x | x <- [2,5..], isPrime x]

I tried to mess around with the filter command but I don't know what I am doing. I am very new to Haskall and functional languages. I got the result of [2,5,11,17,23,29,41,47,53,59] when entering primeskip 10 which doesn't skip properly at 23 to 29.

CodePudding user response：

A possibility consists in developing separately:

a generic function that skips every 2nd element in any list
a function that generates a list of all prime numbers

and then combine these two things in our very last step. This is consistent with the commonly held piece of engineering philosophy:

“Do just one thing but do it well.”

As for the first step, we can use recursion:

everyOther :: [a] -> [a]
everyOther (x:y:zs) = x : everyOther zs
everyOther [x]      = [x]
everyOther []       = []

Regarding the computation of the list of all prime numbers, the Haskell wiki displays a large number of possibilities.

We have to note that the approach of testing primality separately for every single number is massively inefficient. One gains a lot by leveraging the list of previous prime numbers. It is for example redundant to divide a candidate prime by non-prime numbers. A possible code which avoids these drawbacks goes for example like this:

-- limit the search to possible prime factors, below the square root of
-- the candidate:
getBound :: Int -> Int -> Int
getBound n b = let  b1 = b 1
               in   if (b1*b1 > n)  then  b  else  getBound n b1

findNextPrime :: Int -> Int -> Int
findNextPrime k b = if (all (\p -> mod k p /= 0) $ takeWhile (<= b) allPrimes)
                         then  k
                         else  findNextPrime (k 1) (getBound (k 1) b)

genPrimes :: Int -> Int -> [Int]
genPrimes k bound =
    let  np = findNextPrime k (getBound k bound)
    in   np : genPrimes (np 1) (getBound (np 1) bound)

allPrimes :: [Int]
allPrimes = 2 : (genPrimes 3 1)

Finally, we can combine the two above functionalities:

primeSkip :: Int -> [Int]
primeSkip n = take n $ everyOther allPrimes

CodePudding user response：

You want to generate the odd integers, since even numbers are by definition not prime, while odd integers may or may not be prime. You could could prepend 2 to the list of candidates

primeskip n = take n [x | x <- (2:[3,5..]), isPrime x]

but it might be simpler to just prepend it to the result to avoid testing it, as you consider because you know already know it is prime.

primeskip n = 2 : (take (n-1) [x | x <- [3,5..], isPrime x])