Skip to content

Instantly share code, notes, and snippets.

@spencerjanssen
Created October 20, 2015 08:13
Show Gist options
  • Save spencerjanssen/4e5d30698fb072688e0b to your computer and use it in GitHub Desktop.
Save spencerjanssen/4e5d30698fb072688e0b to your computer and use it in GitHub Desktop.
clucky.c: fast lucky number sieve
#include <stdio.h>
#define QMAX 100000001
// we pretend these are 1 indexed, gross...
int seq[QMAX];
int count[QMAX];
// could replace this with a no-op and print the whole thing at the end
void emit_result(int n){
printf("%d\n", n);
}
void sieving(){
int n = 5;
seq[1] = 1;
seq[2] = 3;
emit_result(seq[1]);
emit_result(seq[2]);
count[2] = 0;
int idx = 3;
while(idx < QMAX){
int pos = 2;
for(;;){
if(pos >= idx || seq[pos] > idx){
// we've run out of numbers to check
// number is safe
emit_result(n);
seq[idx] = n;
count[idx] = 0;
n += 2;
idx++;
break;
} else if(count[pos] == 0){
// this has been killed by seq[pos]
// move to the next n
n += 2;
count[pos] = seq[pos]-1;
break;
}
count[pos]--;
pos++;
}
}
}
int main(){
sieving();
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment