Skip to content

Instantly share code, notes, and snippets.

@tos-kamiya
Last active November 2, 2021 04:39
Show Gist options
  • Save tos-kamiya/c9360692e0ca32a90e5511c26f6002df to your computer and use it in GitHub Desktop.
Save tos-kamiya/c9360692e0ca32a90e5511c26f6002df to your computer and use it in GitHub Desktop.
Sieve of Eratosthenes in C
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int *simple_sieve(int limit)
{
char is_prime[limit + 1];
memset(is_prime, 1, limit + 1);
unsigned int count_of_primes = 0;
for (int n = 2; n <= limit; n++) {
if (is_prime[n]) {
count_of_primes += 1;
for (int m = n * n; m <= limit; m += n)
is_prime[m] = 0;
}
}
int *primes = (int *)calloc(count_of_primes + 1, sizeof(int));
unsigned int c = 0;
for (int n = 2; n <= limit; n++) {
if (is_prime[n])
primes[c++] = n;
}
primes[c] = 0; // sentinel
return primes;
}
int main(int argc, char *argv[])
{
int *primes = simple_sieve(100);
for (unsigned int i = 0; i < primes[i] != 0; i++)
printf("%d ", primes[i]);
printf("\n");
free(primes);
return 0;
}
@tos-kamiya
Copy link
Author

tos-kamiya commented Nov 2, 2021

Re-implemented in C99.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment