0

Here is the code I am trying to use: This should generate all primes up to 100

sieve_primes = [x | x<-[2..100], y<-[2..50], z <-[2..25], (x*z) `mod` y /= 0]
Will Ness
  • 70,110
  • 9
  • 98
  • 181
Greg Peckory
  • 7,700
  • 21
  • 67
  • 114
  • If you define `primes` to be the infinite list of prime numbers (as in [this answer](http://stackoverflow.com/questions/26324275/check-whether-an-integer-or-all-elements-of-a-list-of-integers-be-prime/26324612#26324612)), then the solution to your problem is as simple as `take 100 primes`. – jub0bs Nov 10 '14 at 20:44
  • 1
    Jubobs: That would yield the first 100 primes. To get all primes up to 100, use `takeWhile (<= 100) primes`. – hammar Nov 10 '14 at 20:50
  • @hammar Oops, you're right. Sorry, I misread the question. – jub0bs Nov 10 '14 at 20:56
  • @user3237465 when I import the package and run `main = print Prime`, I get an error `Not in scope: data constructor: "Prime"` – Greg Peckory Nov 10 '14 at 21:49
  • 1
    @John Doe, what is that dollar for? Use the library like this: `main = print $ takeWhile (< 100) primes`. – effectfully Nov 10 '14 at 22:01
  • My mistake, I used a capital on the P. Embarrassing. Thanks for the help!. Really appreciate it – Greg Peckory Nov 10 '14 at 22:08
  • 2
    @user3237465 the package you recommend to use appears to be performing *significantly* worse than the faster (likewise immutable) functions from the wiki page (like 6.1 and 3.10, when compiled of course). Mutable arrays code in it is much faster and is still far from being optimized; the [arithmoi package](https://hackage.haskell.org/package/arithmoi-0.4.1.1/docs/Math-NumberTheory-Primes-Sieve.html) should probably be used for that. – Will Ness Nov 11 '14 at 07:24
  • it was wrong to edit out the intent of the OP; I rolled back my edit. – Will Ness Nov 11 '14 at 08:29
  • 1
    The Sieve of Eratosthenes does not use the modulus to detect multiples, it uses addition (or multiplication) to generate them. – molbdnilo Nov 11 '14 at 09:35
  • @Will Ness, yep, you are right. I've been using this package for solving Euler problems for a year, but even 6.1 in the wiki is much better. I deleted my comment. OP, sorry for confusing. – effectfully Nov 11 '14 at 09:54
  • @molbdnilo you're right, but, the code shown doesn't work anyway - the intent of the OP was indeed the SoE of sorts, generating the possible multiples (as I hope is seen more clearly in my now updated answer). – Will Ness Nov 11 '14 at 10:20
  • @user3237465 pity you've removed it, now our comments are orphaned (mine and yours)... the wiki page we both refer to is http://www.haskell.org/haskellwiki/Prime_numbers, and the other package is [here](http://hackage.haskell.org/package/primes-0.2.1.0/docs/Data-Numbers-Primes.html). --- BTW 6.1 is the fastest of the immutable codes there, even without the proper wheel support. :) --- [arithmoi](https://hackage.haskell.org/package/arithmoi-0.4.1.1/docs/Math-NumberTheory-Primes-Sieve.html) is *very* fast. – Will Ness Nov 11 '14 at 10:32
  • Possible duplicate of [Prime Sieve in Haskell](http://stackoverflow.com/questions/11768958/prime-sieve-in-haskell) – Cactus Apr 08 '16 at 03:46

2 Answers2

1

The code

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

computes all the factors just to count them. You don't need to count them: as soon as the second factor is found you can stop your search without checking for further ones.

So, either replace length ... == 1 with a custom predicate, or take 2 elements from the list comprehension before checking its length.

chi
  • 111,837
  • 3
  • 133
  • 218
  • Sorry, my main issue was the first code I put up above. I had the second one working but it was too slow. Made a mistake typing it out was all. I think I'll delete that code. Any idea why the 1st piece of code isn't working? Thanks for the help. – Greg Peckory Nov 10 '14 at 20:29
  • @JohnDoe The first will generate all the `x`s such that __there exist__ `y,z` satisfying the divisor requirement. For instance, `x=6` will be in that list because if we take `y=7, z=1` we get `6*1 mod 7 == 6 /= 0`. This amounts to saying that 7 is not a divisor of 6, hence 6 is prime. – chi Nov 10 '14 at 23:08
0

What you had in mind was probably 

Prelude> [x| x<-[2..100], not $ elem x [y*z| y<-[2..50], z<-[2..25]]]
[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97]

This is very slow. At least we can rearrange the pieces, 

Prelude> [x| let sieve=[y*z| y<-[2..50], z<-[2..25]], 
             x<-[2..100], not $ elem x sieve]
[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97]

This is still very slow, for any number much above even 1000 (where you'd use 500 and 250). Then again, why the 25 (250) limit? Your code follows the 

primes = [x| x<-[2..], not $ elem x 
                       [y*z| y<-[2..x`div`2], z<-[2..min y (x`div`y)]]]

idea, i.e. y*z = 2*y .. min (y*y) x, so with the known top limit (x <= n) it should be

primesTo n = [x| let sieve=[y*z| y<-[2..n`div`2], z<-[2..min y (n`div`y)]],
                 x<-[2..n], not $ elem x sieve]

(incidentally, max (min y (n/y)) {y=2..n/2} = sqrt n, so we could've used 10 instead of 25, (and 31 instead of 250, for the 1000)).

Now 1000 is not a problem, only above ~ 10,000 we again begin to see that it's slow (still), running at n2.05..2.10 empirical orders of growth (quick testing interpreted code in GHCi at n = 5000, 10000, 15000).

As for your second (now deleted) function, it can be rewritten, step by step improving its speed, as

isPrime n = length [x | x<-[2..n], n `mod` x == 0] == 1
          = take 1 [x | x<-[2..n], n `mod` x == 0] == [n]
          = [x | x<- takeWhile ((<=n).(^2)) [2..n], n `mod` x == 0] == []
          = and [n `mod` x > 0 | x<- takeWhile ((<=n).(^2)) (2:[3,5..n])]

now, compiled, it can get first 10,000 primes in few tenths of a second.

Will Ness
  • 70,110
  • 9
  • 98
  • 181