My Math Forum Finding primes...

 Number Theory Number Theory Math Forum

 November 4th, 2008, 09:43 AM #1 Senior Member   Joined: Oct 2007 From: Chicago Posts: 1,701 Thanks: 3 Finding primes... So, I'm sure this isn't terribly hard to find on my own, but CRG will probably drool while answering this one ( ). Anyway, I've started playing around with Project Euler (using it to learn Haskell...). Anyway, a lot of the problems deal with primes, and I figure I should look into effective ways of computing them... Is there a cleaner (or faster) way than the Sieve of Eratosthenes? There are slight improvements on it, correct? What I should do is just compute primes for 24 hours or so, and store those in a file, so I can access them whenever I want. Also, CRG, do you know anything about Project Euler?
November 4th, 2008, 10:11 AM   #2
Global Moderator

Joined: Nov 2006
From: UTC -5

Posts: 16,046
Thanks: 938

Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms
Re: Finding primes...

Quote:
 Originally Posted by cknapp CRG, do you know anything about Project Euler?
I have an account, though I don't know that I'm doing all that well. I think I'm at level 2.

Quote:
 Originally Posted by cknapp Anyway, I've started playing around with Project Euler (using it to learn Haskell...). Anyway, a lot of the problems deal with primes, and I figure I should look into effective ways of computing them... Is there a cleaner (or faster) way than the Sieve of Eratosthenes? There are slight improvements on it, correct?
I have a list of methods that I recently put together, but it wouldn't be of much interest to you. Most of the methods on my list are very complicated to implement, and aren't well-suited for your (apparent) task: generating a list of primes from 1 to n for some large n.

To make the Sieve of Eratosthenes fast, you want to:
* use a bit array to store numbers, rather than an array of bools (32-fold storage improvement)
* store only odd numbers, or maybe only numbers +/- 1 mod 6 (2-3-fold storage improvement, 2-fold speed improvement)

If you run out of memory, there are a number of other improvements possible. In fact you can reduce the storage space from n to as little as sqrt(n) with some effort -- this is called 'segmenting' the sieve.

A good sieve implementation rivals the hard drive in speed. It's not clear whether time would actually be saved reading the file off the hard drive (unless the list is too big for memory, of course!).

 November 4th, 2008, 12:11 PM #3 Senior Member   Joined: Oct 2007 From: Chicago Posts: 1,701 Thanks: 3 Re: Finding primes... Hmm... I guess one thing that's strange about what I'm doing is that Haskell acts in funny ways... For example, the code I have is: Code: primes :: [Integer] primes = sieve [2..] where sieve (p:xs) = p : sieve [x|x <- xs, x mod p > 0] However, I found a site with better ways of doing things... that is apparently very computation heavy... So, I'll start looking for better implementations. My main problem is that I don't know what's really going on with Haskell... If it makes you happy, another implementation on a similar page has (which is still not the best implementation it has... Code: primes :: [Integer] primes = 2:filter isPrime [3,5..] where isPrime n = all (not . divides n) \$ takeWhile (\p -> p*p <= n) primes divides n p = n mod p == 0 Which only looks at odds . Anyway, once I actually figure out what the second slice of code is doing, I can try to explain it. Edit: That second implementation works about 50 times faster for the first 10000 primes...
 November 5th, 2008, 12:06 PM #4 Global Moderator     Joined: Nov 2006 From: UTC -5 Posts: 16,046 Thanks: 938 Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms Re: Finding primes... The second piece of code checks each odd number by testing up to its square root. This is an O(n^1.5) algorithm, very inefficient. (Actually, since you test only primes, it's O(n^1.5/log n), but that's not much better.) What you want to do is something like this (imperative pseudocode): Code: bitarray b = all_ones(1000000000); // 1 billion bits = 125 MB b[0] = 0; // 0*2+1 = 1 is not prime int[] smallPrimes = primes(sqrt(2000000000)); // list of odd primes up to 44721 for (p in smallPrimes) { for (i = (p >> 1) + p; i < 1000000000; i += p) b[i] = 0; } where b[n] represents the primality of 2*n + 1.
 November 6th, 2008, 12:00 PM #5 Senior Member   Joined: Oct 2007 From: Chicago Posts: 1,701 Thanks: 3 Re: Finding primes... Thanks. I'll get on that... but I just remembered I have a large-ish project due in not too terribly long... Although when I'm done with that, I'll probably be better at Haskell, and I'll be able to implement it.

 Tags finding, primes

 Thread Tools Display Modes Linear Mode

 Similar Threads Thread Thread Starter Forum Replies Last Post caters Number Theory 67 March 19th, 2014 04:32 PM Akcope Number Theory 4 October 20th, 2013 04:05 AM mathbalarka Number Theory 3 June 27th, 2013 05:33 PM johnr Number Theory 20 April 9th, 2013 05:49 PM metinsariyar Number Theory 10 May 12th, 2011 11:09 AM

 Contact - Home - Forums - Cryptocurrency Forum - Top