Skip to content

Instantly share code, notes, and snippets.

@EmilHernvall
Created May 3, 2011 17:29
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 EmilHernvall/953778 to your computer and use it in GitHub Desktop.
Save EmilHernvall/953778 to your computer and use it in GitHub Desktop.
Translation of someone elses code for a more sophisticated prime sieve
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
int main(int argc, char** argv)
{
if (argc != 2) {
printf("usage: genprimes2 num\n");
return 0;
}
int limit = atoi(argv[1]);
if (limit < 10) {
printf("the upper bound must be at least 10\n");
return 0;
}
int sieveBound = floor((limit-1)/2.0);
char *sieve = (char*)calloc(sizeof(char), sieveBound+1);
int crossLimit = floor((floor(sqrt(limit))-1)/2.0);
int i, j;
for (i = 1; i <= crossLimit; i++) {
if (sieve[i]) {
continue;
}
for (j = 2*i*(i+1); j < sieveBound+1; j += 2*i+1) {
sieve[j] = 1;
}
}
printf("2\n");
for (i = 1; i <= sieveBound; i++) {
if (!sieve[i]) {
printf("%d\n", 2*i+1);
}
}
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment