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:
Quote:
To make the Sieve of Eratosthenes fast, you want to: * use a bit array to store numbers, rather than an array of bools (32fold storage improvement) * store only odd numbers, or maybe only numbers +/ 1 mod 6 (23fold storage improvement, 2fold 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 [xx < xs, x `mod` p > 0] 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 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; } 
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 largeish 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  

Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
primes and twin primes: Number between powers of 10  caters  Number Theory  67  March 19th, 2014 04:32 PM 
Finding all primes that satisfy a condition  Akcope  Number Theory  4  October 20th, 2013 04:05 AM 
(p, p+4)Primes  mathbalarka  Number Theory  3  June 27th, 2013 05:33 PM 
n^2+1 n^2+n+1 primes  johnr  Number Theory  20  April 9th, 2013 05:49 PM 
Primes Between an  bn ,always?  metinsariyar  Number Theory  10  May 12th, 2011 11:09 AM 