Skip to content

Instantly share code, notes, and snippets.

@Zeta611
Last active February 24, 2020 01:12
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save Zeta611/6f301528621e58825148d7ee61e95596 to your computer and use it in GitHub Desktop.
Save Zeta611/6f301528621e58825148d7ee61e95596 to your computer and use it in GitHub Desktop.
[Sieve of Eratosthenes in C] #algorithm
/**
* sieve.c
*
* Created by Jay Lee on 08/25/2019.
* Copyright © 2019 Jay Lee <jaeho.lee@snu.ac.kr>
* This work is free. You can redistribute it and/or modify it under the
* terms of the Do What The Fuck You Want To Public License, Version 2,
* as published by Sam Hocevar. See http://www.wtfpl.net/ for more details.
*/
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <math.h>
#include <time.h>
#define SIZE 10000
void generate_sieve(bool *sieve, int cnt)
{
int bound = sqrt(cnt - 1);
for (int p = 2; p <= bound; ++p) {
if (!sieve[p]) {
for (int n = p * p; n < cnt; n += p) {
sieve[n] = true;
}
}
}
}
int main(void)
{
clock_t start = clock();
/* malloc for large SIZE's */
bool *sieve = malloc(sizeof(bool[SIZE]));
sieve[0] = sieve[1] = true;
generate_sieve(sieve, SIZE);
int cnt = 0;
int i, j;
for (i = 0; i < SIZE; ++i) {
cnt += !sieve[i];
}
int *primes = malloc(sizeof(int[SIZE]));
for (i = j = 0; i < SIZE; ++i) {
if (!sieve[i]) {
primes[j++] = i;
printf("%d ", i);
}
}
printf("\n");
free(sieve);
free(primes);
clock_t end = clock();
float seconds = (float)(end - start) / CLOCKS_PER_SEC;
printf("Took %f seconds\n", seconds);
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment