• Advertisement
Sign in to follow this  

Sieve of Eratosthenes

This topic is 3081 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

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 = 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
Advertisement
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
Sign in to follow this  

  • Advertisement