Sign in to follow this  
Arjan B

Sieve of Eratosthenes

Recommended Posts

For a homework assignment, I'm to implement the Sieve of Eratosthenes in C. I think I'm doing it correctly but I am given wrong output (such as the number 989, which isn't prime). Could anyone check my code to see if they see any mistakes? prime.h:
#define NROF_SIEVE 1000

static unsigned long long buffer[(NROF_SIEVE/64)+1];

prime.c:
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

#include "prime.h"

void InitBuffer(void);
bool IsPrime(long n);
void Strike(long n);
void StrikeMultiplesOf(long n);
long NextPrime(long n);
void PrintPrimes(void);

int main ()
{
    InitBuffer();
    
    long p;
    for (p = 2; p*p < NROF_SIEVE && p != -1; p = NextPrime(p)) {
    	StrikeMultiplesOf(p);
    }
    
    PrintPrimes();    
    
    return (0);
}

// Initializes all the values in buffer to 0
void InitBuffer(void) {
	long i;
	for (i = 0; i < (NROF_SIEVE/64)+1; ++i) {
		buffer[i] = 0;
	}
}

// Returns whether n is prime
bool IsPrime(long n) {
	return (buffer[n/64] & 1<<(n%64)) == 0;
}

// Strikes n off the list of primes
void Strike(long n) {
	buffer[n/64] |= 1<<(n%64);
}


// Strikes all multiples of n (except n itself) off the list of primes
void StrikeMultiplesOf(long n) {
	long i;
	for (i = n+n; i < NROF_SIEVE; i += n) {
		Strike(i);
	}
}

// Returns the prime after n, or -1 if there is no prime after n
long NextPrime(long n) {
	long i;
	for (i = n+1; i < NROF_SIEVE; ++i) {
		if (IsPrime(i)) return i;
	}
	return -1;
}

// Prints all the primes in buffer
void PrintPrimes(void) {
	long i;
	for (i = 1; i < NROF_SIEVE; ++i) {
		if (IsPrime(i)) printf("%li is prime.\n", i);
	}
}

Thank you in advance, Arjan

Share this post


Link to post
Share on other sites
The result of 1<<count is undefined if count is greater than 31. Try 1LL instead of 1 and tell us if that works.

By the way, you don't gain anything by using long long for the array. Just use int and you should be fine. Or don't use an array at all, 1000 bytes is not the end of the world ;)

[Edited by - DevFred on September 14, 2009 8:15:29 AM]

Share this post


Link to post
Share on other sites
That fixed the problem, thank you very much!
We were given a template in which the buffer was defined that way, so I'll leave it that way to keep the teachers happy ^^.

[Edited by - Arjan B on September 14, 2009 1:53:07 PM]

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this