Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

I've been trying to solve a class of problems that require the generation of 1st n prime numbers. Now, n may be large, so completely fitting (2..n) in memory as required by some sieve techniques isn't possible. At the first go, I'd tried something like this:

def prime_sieve(n):
  result = []
  for i in xrange(2,n+1): #iterate over 2..n
    ok = True             

    for j in result:
      #if any of the already generated primes
      #divides the next number, set flag and break
      if i % j == 0:
        ok = False       
        break

    if ok: result.append(i)

  return result

until I realized that it was very naive. I haven't been able to find a decently compact and efficient implementation. Do you have any ideas/suggestions? I have written very verbose Python here so that even the non-Pythonic people can shoot suggestions at me :)

share|improve this question
2  
There is a good algorithm in this answer: stackoverflow.com/questions/567222/… –  murgatroid99 Oct 9 '11 at 1:54
    
please post this as an answer and let me accept it. This is insanely efficient! Thanks –  yati sagade Oct 9 '11 at 8:59
    
Coding questions should be asked on Stack Overflow. I won't migrate this as (as others have pointed out) it's already been asked and answered over there. –  ChrisF Oct 9 '11 at 19:06
    
Thanks ChrisF for pointing that out, but I thought my question on SE-P can be about "algorithm and data structures concepts". I was asking for a memory-efficient and fast implementation of the sieve, in any language - just the technique mattered. Correct me if I'm wrong. –  yati sagade Oct 9 '11 at 21:26
add comment

closed as off topic by ChrisF Oct 9 '11 at 19:06

Questions on Programmers Stack Exchange are expected to relate to software development within the scope defined by the community. Consider editing the question or leaving comments for improvement if you believe the question can be reworded to fit within the scope. Read more about reopening questions here.If this question can be reworded to fit the rules in the help center, please edit the question.

4 Answers

Firstly: you needn't test i bigger than sqrt(n). The whole idea of the sieve is, that more and more non-primes are "sieved away". Therefore, once you reach sqrt(n) all non-sieved numbers do not have prime factors smaller than sqrt(n) and are smaller than n and are thus prime.

You can also simply reduce the running time by simply restricting yourself to odd numbers, but I'll leave that up to you.

Here's some haXe code for it:

function sieve(n) {
     //init sieve
     var isPrime = [false, false];
     for (i in 2...n) 
         isPrime[i] = true;

     //sieve out any divisble numbers
     for (p in 2...Std.int(Math.sqrt(n)) 
         if (isPrime[p] == false) continue;
         else 
             for (i in 1...Std.int(n / p))
                 isPrime[i * p] = false;

     //collect what's left
     var ret = [];
     for (i in 0...isPrime.length)
         if (isPrime[i])
            ret.push(i);
     return ret;
}
share|improve this answer
    
ok, but this function prime_sieve is called with sqrt(m) where m is the big number. Also, I have not a clue about JS memory mgmt, but how efficient is this impl? As my impl (yes, called with sqrt(m)) takes verrry long if m is a 12 digit number. –  yati sagade Oct 8 '11 at 23:44
    
@Caleb: That's exactly what's happening. My point was simply, that there's no big use in running the first iteration for 2, since it will merely tell you, that all other even numbers are not prime - surprise!!! ;) –  back2dos Oct 9 '11 at 0:03
    
@yatisagade: Well, you would probably write such a thing in C and store the flags in a block of bits. So you can store the sieve for 32 bit integers in 128MB of memory, which is fair enough. This is merely intended to illustrate the idea. I've checked wikipedia and they also only seem to give that answer. You can use ratchets idea to reduce memory consumption, if that's really necessary. –  back2dos Oct 9 '11 at 0:13
    
@back2dos, ah, right... I should've read your code more carefully. Agree that it's a useful optimization. –  Caleb Oct 9 '11 at 0:17
    
@yatisagade: As for speed, I've seen no pointers to a more scaleable solution. At least nowhere near hardcoding. –  back2dos Oct 9 '11 at 0:17
show 2 more comments

First of all, you can iterate from 3 .. n skipping every other number. Second, what kind of scale of "large" do you mean n can be? Could you just hard-code and preload some number of known primes? (http://www.bigprimes.net/) Is there any reason to do the work over each time you need it? Then just iterate from the highest by twos if you still need more than 1.4 billion of them.

share|improve this answer
    
I tried with 12 digits - horribly slow. Yes, in the end, I think I'll have to fall back on hard coding a reasonably large set. But let's see if anything nice comes up :) –  yati sagade Oct 8 '11 at 23:46
1  
Well, the reason primes are so useful is the difficulty of dealing with them, even with lightning fast algorithms and hardware. I think what you may be asking for here would be a number theory breakthrough. How many reputation points does stack exchange give for a Nobel Prize winning answer? Is there a badge for that? :-) –  kylben Oct 9 '11 at 0:02
    
hahaa.. was reading a wiki article - It took hundreds of machines and 2 years till '09 to prime-factorize a 232 digits long number!! en.wikipedia.org/wiki/Integer_factorization –  yati sagade Oct 9 '11 at 0:12
add comment

you could chunk the generation so you don't need to keep 2-n in memory but only a small portion of them

you can then use external memory to store already generated primes which you can read again for the first filter passes

share|improve this answer
add comment

The algorithm is known as the Sieve of Eratosthenes:

  1. Initialize an array of integers 1..n. Set x = 1.
  2. Let x be the next non-zero number in the array. (So, in the first case, x=2.)
  3. Iterate over the array stepping by x. Set each number you encounter to 0. (So, in the first case, you'd keep 2, but eliminate 4, 6, 8...)
  4. If x <= sqrt(n), go back to step 2.
  5. The non-zero numbers left in the array are all prime.

This takes the "you can skip every other number" idea and extends it to skipping every composite number. I don't think you can make the sieve any more efficient than this.

Note: I used an array of consecutive integers above because it's easy to understand the algorithm that way. This isn't the most efficient method, though, since all you really need is a prime/not prime flag at each index. So, for example, you could reduce the space required by a factor of 8 * sizeof(int) by using bits for each number instead of ints.

share|improve this answer
    
yeah I guess so. This combined with ratchet freak's idea of segmenting the input list can do the trick I guess. –  yati sagade Oct 8 '11 at 23:50
    
This solution is practically identical to mine, except that you use an array of integers, whereas I use an array of flags. For 32 bit integers, in a compact version my solution would use 1/32 the space. There's simply no point in storing the integers, because it's index is already its value. –  back2dos Oct 9 '11 at 0:01
    
@back2dos, that's why I voted your answer up once I finished typing mine. ;-) I agree about storage -- see my note about that. –  Caleb Oct 9 '11 at 0:09
add comment

Not the answer you're looking for? Browse other questions tagged or ask your own question.