1 reply to this topic

[TkTech]

Made it for a question posted on the forums. Its a simple and fast method of finding all of the primes up to and including a certain number.

Its pretty simple, anyone should be able to get what its doing. The only requirement is basic math and a knowledge of bit arrays.

/* (C) 2009 Tyler Kennedy */
#include <stdlib.h>
#include <stdio.h>
#include <math.h>

#define NumberToFind 757

#define SetBit(d,c)     ((d) |= (1L << (c)))
#define TestBit(d,c)    ((d) &  (1L << (c)))

int main(void)
{
    /* Implements the Sieve Of Eratostheness, a simpler version of the Sieve of Atkins */
    unsigned char prime[(NumberToFind / 8)+1] = {0};
    int x,y,t = NumberToFind;
    
    prime[0] |= 3; //Set the first two bits to 0...0011 - 0 and 1 are both non-prime.
    
    for(x = 2; x < (int)(sqrt(NumberToFind)+1); x++)
    {
        if(TestBit(prime[x/8],((x % 8))) == 0)
        {
            for(y = x*x; y < NumberToFind; y+=x)
                SetBit(prime[y/8],(y % 8));
        }
    }
    
    for(x = 0; x < NumberToFind+1; x++)
    {
        if(TestBit(prime[x/8],(x % 8)) == 0)
            printf("%d\n",x);
    }   
    
    fgetc(stdin);
    
    return 0;
}

Edited by TkTech, 03 October 2009 - 05:22 PM.