links

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

The sieve of eratosthenes

Objective C

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

#import <objc/Object.h>
#import <stdio.h>
#include <stdlib.h>

@interface Sieve : Object {
    int *primes;
    int limit;
}

- (Sieve *) init: (int) lim;
- (void) setup: (int) lim;
- (void) generatePrimes;
- (void) printPrimes;
- (void) removeMultiples: (int) base;
- (int)  nextPrime: (int) currPrime;
- (void) free;
@end

@implementation Sieve

- (void) setup: (int) lim {
    int i;
    limit = lim;
    primes = malloc(sizeof(int) * (lim + 1));
    primes[0] = primes[1] = 0;
    for(i = 2; i <= lim; i++) {
        primes[i] = 1;
    }
}

- (Sieve *) init: (int) lim {
    self = [super init];

    if(self) {
        [self setup: lim];
    }
    return self;
}

- (void) generatePrimes {
    int currPrime = 2;

    while((currPrime * currPrime) <= limit) {
        [self removeMultiples: currPrime];
        currPrime = [self nextPrime: currPrime];
    }
}

- (void) printPrimes {
    int i;
    for(i = 0; i <= limit; i++) {
        if(primes[i]) {
            printf("%d ", i);
        }
    }
    printf("\n");
}

- (void) removeMultiples: (int) base {
        int i;
        for(i = base + base; i <= limit; i += base) {
            primes[i] = 0;
        }
}

- (int) nextPrime: (int) currPrime {
        int i;

        for(i = currPrime + 1; i <= limit; i++) {
            if(primes[i])
                break;
        }
        return i;
}

- (void) free {
    free(primes);
    [super free];
}
@end

int main(int argc, const char *argv[]) {
    int limit;
    Sieve *s;

    limit = atoi(argv[1]);
    s = [[Sieve alloc] init: limit];

    [s generatePrimes];
    [s printPrimes];

    [s free];
    return 0;
}

back to Eratosthenes page

stats

It is Saturday May 17, 2008 10:57 am
This page served 530 times
This page last modified: April 14, 2008 11:28 am
Your IP address is: 38.103.63.17
You are browsing using: CCBot/1.0 (+http://www.commoncrawl.org/bot.html)
You are browsing from: United States.
badcomputer.org's uptime: 10:57:58 up 23 days, 11:40, 0 users, load average: 0.00, 0.00, 0.00