links

< home >
< unix stuff >
< code >
< writing >
< archive >
< music >
< photos >
< recipes >
< site map >
< about badcomputer >

sieve of eratosthenes

C

/* Sieve of Eratosthenes in C
 * Written by Rob Hoelz
 */

#include <stdio.h>
#include <stdlib.h>
#define getbit(arr, index) (arr[index / 8] & 0x80 >> index % 8)
#define clearbit(arr, index) (arr[index / 8] &= ~(0x80 >> index % 8))

void initSieves(unsigned char *sieves, int limit);
void generatePrimes(unsigned char *sieves, int limit);
void removeMultiples(unsigned char *sieves, int limit, int currPrime);
int nextPrime(unsigned char *sieves, int limit, int currPrime);
void printPrimes(unsigned char *sieves, int limit);

int main(int argc, char **argv) {
    int limit;
    unsigned char *sieves = NULL;

    if(argc == 1) {
        return 0;
    }
    limit = atoi(argv[1]);
    sieves = malloc(limit / 8 + 1);
    if(! sieves) {
        return 0;
    }
    initSieves(sieves, limit);
    generatePrimes(sieves, limit);
    printPrimes(sieves, limit);
}

void initSieves(unsigned char *sieves, int limit) {
    int i;
    *sieves++ = 0x3f;
    for(i = 8; i <= limit; i += 8) {
        *sieves++ = 0xff;
    }
}

void generatePrimes(unsigned char *sieves, int limit) {
    int currPrime = 2;
    while(currPrime * currPrime <= limit) {
        removeMultiples(sieves, limit, currPrime);
        currPrime = nextPrime(sieves, limit, currPrime);
    }
}

void removeMultiples(unsigned char *sieves, int limit, int currPrime) {
    int i;

    for(i = currPrime << 1; i <= limit; i += currPrime) {
        clearbit(sieves, i);
    }
}

int nextPrime(unsigned char *sieves, int limit, int currPrime) {
    currPrime++;
    for(; currPrime <= limit; currPrime++) {
        if(getbit(sieves, currPrime)) {
            return currPrime;
        }
    }
    return currPrime;
}

void printPrimes(unsigned char *sieves, int limit) {
    int i;
    for(i = 0; i <= limit; i++) {
        if(getbit(sieves, i)) {
            printf("%d ", i);
        }
    }
    printf("\n");
}

back to Eratosthenes page

stats

It is Monday September 08, 2008 1:17 am
This page served 1038 times
This page last modified: April 14, 2008 11:28 am
Your IP address is: 38.103.63.61
You are browsing using: CCBot/1.0 (+http://www.commoncrawl.org/bot.html)
You are browsing from: United States.
badcomputer.org's uptime: 01:17:36 up 39 days, 16:24, 2 users, load average: 0.02, 0.03, 0.00