#include "stdio.h" #include "stdlib.h" struct list { int i; struct list * next; } *first, *last; void add_prime(){ int i=last->i+1; while(!check_prime(i))i++; last->next = malloc(sizeof(struct list)); last=last->next; last->i=i; last->next=NULL; //printf("add %d",i); } int check_prime(int i){ if(i>last->i*last->i) add_prime(); struct list *p=first; while(i%p->i) if(p->next) p=p->next; else return 1; return 0; } int main(int argc,char ** argv){ printf("%d\n",2); int lim; if(argc==1)lim=100; else sscanf(argv[1],"%d",&lim); first=last=malloc(sizeof(struct list)); first->i=2; first->next = NULL; int i=2; while(++i<lim) if(check_prime(i)) printf("%d\n",i); }

It uses a linked list to store all primes that are necessary. In particular, to save space, it only stores primes that are actually necessary to prove the others' primacy. Please post comments and suggestions.