# Sieve of Eratosthenes

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

## 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);
}
}



##### 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 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]

1. 1
2. 2
3. 3
Rutin
15
4. 4
5. 5

• 13
• 26
• 10
• 11
• 9
• ### Forum Statistics

• Total Topics
633731
• Total Posts
3013582
×