CODEWITHSUNDEEP
haskell
Stormy
Stormy

Reputation: 169

nth Prime, and Prime Factors

Going through the Haskell tutorial, it said to write a function 'isPrime' to determine if a number is a prime number.

I came up with:

isPrime :: Integer -> Bool
isPrime n = factors n == [1,n]
    where factors n = [x | x <- [1..n], n `mod` x == 0]

which works.

But how would I go about asking for the nth prime number -- as in, the 100th prime number is 541?

Playing around further with primes, I found a list of Prime Factors like this:

primeFactors :: Integer -> [Integer]
primeFactors n = filter prime (factors n)
    where factors n = [x | x <- [1..n], n `mod` x == 0]
          prime n = factors n == [1,n]

and that works, too.

However, when you put in a very large number, you get significant lag time.

As an example, it does these just fine:

ghci > primeFactors 419
[419]

ghci > primeFactors 5698
[2,7,11,37]                 -- did this one really fast...

ghci > primeFactors 76586
[2,149,257]                 -- and this one really fast... 

ghci > primeFactors 876350
[2,5,17,1031]               -- it hung up just a hair with this one...

ghci > primeFactors 4287635
[5,11,19,373]               -- hung up a little bit longer here...

ghci > primeFactors 34598274
[2,3,5766379]               -- hung up for quite a while here...

ghci > primeFactors 208346758
[2,104173379]               -- and for a very long time with this one!

The tutorial suggested finding the prime factors of 62451532000, and on that one, I'm still waiting, after somewhere around 5 minutes.

What is causing the lag time, and what would be the best way to speed this up?

Upvotes: 1

Views: 833

Answers (3)

fp_mora
fp_mora

Reputation: 714

Yes, the consensus is the factor list [1..n]. It speeds things up when you minimize the factor list without losing effectiveness. I use a limited factor list that works. It assumes all primes are one-of-4 out of every 10, that is [11,13,17,19,21,23,27,29,31...]. The following starts at 11 (specified) because starting at 1 would include 1 and 9. All primes after 7 end in 1,3,7 or 9. This list eliminates evens and 5s. The following eliminates 3s as well.

no2s3s5s = scanl (\b a -> a + b) 11 $ cycle [2,4,2,4,6,2,6,4]

The length of the factor list need not exceed sqrt n, so ...

fa n=[x|x<-2:3:5:7:(take (floor.sqrt.fromIntegral$n+2) no2s3s5s),mod n x == 0]

fa lists factors, a lot of which are prime

fa 909090 OR fa 121
[2,3,5,7,13,37,91,259,481,3367] AND [11] recpectively

To remove the non-prime from the list

pr n = (null $ fa n) || (fa n == [n])

and

[ d | d<-2:3:5:7:(take 200 no2s3s5s), pr d ]

Produces a prime list but is slow as are all such functions that use a factor list or divisors such.

Upvotes: 0

Jorge Adriano Branco Aires
Jorge Adriano Branco Aires

Reputation: 2300

You can easily get rid of prime. A small change in your algorithm is enough for you to make sure than any new factor you find is guaranteed to be prime.

Here is how you do it. Every time you find an x divides n you remove all x factors from n and then proceed with that new value.

Consider the following example with number 40. Note that 40 = 2^3*5. So 40 is divisible by 1, 2, 4, 5, 8, 20 and 40. We begin testing for prime factors at 2. 

40 `mod` 2 == 0

So 2 is a factor (and prime). So let's remove all the 2's 

40 `mod` 2 == 0
40 `div` 2 == 20

20 `mod` 2 == 0
20 `div` 2 == 10

10 `mod` 2 == 0
10 `div` 2 == 5

5 `mod` 2 == 1

So we removed all the 2's from 40, until we got 5. Now we proceed with 5 instead. You check division by 3, then 4, then 5 which works. And note how 5 is indeed prime.

Now here is a question for you to think about. How does this method guarantee that each new factor you find is prime?

Note: Keep in mind however that while the method above should speed things up when dealing with big numbers composed of relatively small prime factors, it won't do much if you test it e.g. with a big prime number.

Upvotes: 2

merlyn
merlyn

Reputation: 2361

The lag time is due to the factors function. It iterates from 1 to n. So, if n is 62451532000, there will at least be 62451532000 steps. That's too many steps.

There are plenty of ways to speed this up. There's actually so many that one could write a book on it. I suggest you lookup factorization.

For now, try implementing this simple trick. Whenever d is a factor of n, so is n/d. If you look for all factors below √n, and utilize this trick, you would have found all the factors.

This would decrease the number of steps required from 62451532000 to about 250000. Much more manageable.

Upvotes: 6

Related Questions