My Math Forum  

Go Back   My Math Forum > College Math Forum > Number Theory

Number Theory Number Theory Math Forum


Reply
 
LinkBack Thread Tools Display Modes
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?
cknapp is offline  
 
November 4th, 2008, 10:11 AM   #2
Global Moderator
 
CRGreathouse's Avatar
 
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!).
CRGreathouse is offline  
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...
cknapp is offline  
November 5th, 2008, 12:06 PM   #4
Global Moderator
 
CRGreathouse's Avatar
 
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.
CRGreathouse is offline  
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.
cknapp is offline  
Reply

  My Math Forum > College Math Forum > Number Theory

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





Copyright © 2019 My Math Forum. All rights reserved.