Calculating PrimeNumbers

[Skeen]

So I've been working on two small programs to calculate prime numbers, fast and memory efficiently. Both my algorithms are based upon the 'Sieve of Eratosthenes', and I know that the 'Sieve of Atkin' would be the way to go since its faster, however I'm just trying to optimize the one I got, so currently, I've got 2 different codes;

• The first one, is using quite some memory (about 30mb when calculating 3-10.000.000);
• The another one, which is using a lot less memory (about 3mb with the same domain), however the last one is a lot slower (about x10), so it's 10x smaller in memory

First question, which one would you prefer?

I'm somewhat interested in fixing the slower one (due to the smaller memory usage), and really, it's quite buggy;

• First bug: It only allows me define up to 10.000.000, if I go higher it just crashes? - why? (limitation in bitset?)
• Second bug: Why is it slower? (and how to make it faster)
• Third bug: This algorithm (bitset one), got all numbers from 0-max, however the original one, only builds a buffer with the odd ones from 3-max, does anyone see how I'm able to fix the bitset to only add the odd ones? (without really screwing over the logic (or by doing so), as that would reduce the memory needs by 50% :))

Anyone able to help or something? - Code posted below.

Original (fast, somewhat high memory usage)

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define TYPE register unsigned int

int main()
{
    TYPE n, p=1, i=0, j, count=1;
    register bool done;
    register clock_t Time;

    printf("250.000.000 = ~500mb ram..\n\n   Calculate primes up to: ");
    scanf("%d", &n);
    printf("\nCalculating...\n");
    n /= 2;       
    
    TYPE *buffer = (unsigned int*)malloc(n * sizeof(unsigned int));  
    if (buffer == 0)
    {
        printf("Could not allocate RAM!\n\n");
        return 0;
    }
    Time = clock();
    
    for (i=0; i != n; i++)
        {
        buffer[i] = i*2+3;
        }
        
    i = 0;
    
    while (1)
    {
        done = true;
        for (j=i; j < n; j++)
        {
            if (buffer[j] > p)
            {
                p = buffer[j];
                done = false;
                break;
            }
        }
    i = j+1;
    if (!done)
       {
       while (j+p < n) buffer[j+=p] = 0;
       } 
    else 
       {
       break;
       }         
    }
    
    for (unsigned int i=0; i != n; i++)
    {
        if (buffer[i])
        {
            count++;
        }
    }
    
    printf("\n...Calculation done :)\n %d Primenumbers found in %1.3f seconds!\n", count, (clock()-Time)/(float)CLOCKS_PER_SEC);
    free(buffer);
    
    system("PAUSE");
    return 0;
}

Bitset one! (Low Memory usage, somewhat slow)

#include <iostream>
#include <time.h>
#include <bitset>
using namespace std;

#define SHOWOUTPUT
#define MaxValueToReach 10000000

int main()
{
    register unsigned int MaxValue=MaxValueToReach, Worker = 0, OldWorker = 0, LoopController = 0;
    clock_t Time;
    
    bitset<MaxValueToReach+1> ISNOTAPRIMENUMBER; 
    
    ISNOTAPRIMENUMBER.reset();
    
    ISNOTAPRIMENUMBER.set(0);
    ISNOTAPRIMENUMBER.set(1);
    
    Time = clock();
    
    while(1)
        {
        OldWorker=Worker;
        for (LoopController = (Worker+1); LoopController < MaxValue; LoopController++)
            {
            if (ISNOTAPRIMENUMBER.test(LoopController)==false)
               {
               Worker=LoopController;
               break;
               }
            }
        if (OldWorker == Worker){break;}
        
        for (LoopController = (Worker+Worker); LoopController <= MaxValue; LoopController += Worker)
            {
            ISNOTAPRIMENUMBER.set(LoopController);
            }        
        }
    
    float TimeElapsed = ((clock()-Time)/(float)CLOCKS_PER_SEC);
    
    int Counter=0;
    for (int LoopController=0; LoopController<MaxValue; LoopController++)
        {
        if (ISNOTAPRIMENUMBER.test(LoopController)==false)
           {
           Counter++;
           #ifdef SHOWOUTPUT
           cout << LoopController << "\t";
           #endif
           }
        }
    #ifdef SHOWOUTPUT
    cout << endl << endl;
    #endif 
 
    cout << "Calculation done! " << Counter << " Primenumbers in " << TimeElapsed << " seconds!" << endl;
    
    cin.get();
    return 0;
}