The most efficient method to compute primes

for(i=2;i<MAXX;i++)
  {
    if(nos[i]==0) //If the number is not prime i.e crossed out
       continue;
//insert printf here because we know number is prime
printf("%d\r\n",i)
    for(j=2*i;j<MAXX;j+=i)
       nos[j]=0; //If it is prime cut from list all its multiples
   }

struct{
  int value;
  linked *prev;
  linked *next
}linked;

linked todo[1000];
linked *erased,*erasedTail;
for(a=0 to 1000)
{
   todo[a].value=a;
   todo[a].prev=&(todo[a-1]);
   todo[a].next=&(todo[a+1]);
}
todo[0].next=&(todo[2]);
todo[2].prev=&(todo[0]);
erased=&(todo[1]);
erasedTail=&(todo[1]);
erased->next=erased->prev = null;
//then
while(todo[0].next)
{
  int remove=todo[0].next->value
  printf("%d, ",remove);
linked *eraser=&erased;
while(eraser)
{
  int nextvalue=remove*eraser->value;
  if(nextvalue<1000)
  {//starting with the linked list sorted in memory is the major part I was overlooking
    todo[nextvalue].next->prev=todo[nextvalue].prev;
    todo[nextvalue].prev->next=todo[nextvalue].next;
    erasedTail->next=&(todo[nextvalue]);
    erasedTail=erasedTail->next;
    erasedTail->next=null;
  }else{//this else is the other part I overlooked
    eraser->prev->next=eraser->next;
  }
  eraser=eraser->next;
}
//
}

todo[N-1].next=0;

if(todo[nextvalue].next!=0) todo[nextvalue].next->prev=todo[nextvalue].prev;[\code]

makes sure we don't try getting members from a null pointer.

I also included a linked* previous so that we can erase stuff from the erased list (it's one link only, so we cannot use eraser->prev->next=eraser->next;)

rules are:

nextvalue<1000 : add previous = eraser; at the end of the block

else case becomes:

[code]previous->next=eraser->next; //one link used
    if(eraser==erasedTail) erasedTail=previous; //danger: bad case

#include <stdio.h>
#include <memory.h>

// we're checking numbers 0..2*upto; 'uptoSqrt2' is sqrt(upto/2)
enum { upto=18000000, uptoSqrt2=3000 };
// 'is' is a bit-array; bit with value 1 means the number is prime
// the array contains only info for odd numbers
// example: is[0]==(MSB)01101110(LSB) means 1 (LSB) isn't prime; 3,5,7 is, 9 isn't, 11,13 is, 15 isn't
unsigned char is[upto/8+2];

void generate() {
    unsigned i,j;
    memset(is,0xff,sizeof(is));
    is[0]=254; // 1 is not prime => first bit is set to 0
    for (i=1; i<uptoSqrt2; ++i) { // checks whether 2*i+1 is prime
        if (is[i>>3]&(1<<(i&7))) { // if it is => zero all its multiples
            for (j=2*i*(i+1); j<upto; j+=2*i+1) is[j>>3]&=~(1<<(j&7));
        }
    }
}
int isPrime(unsigned a) { // works for a<=2*upto
    if (a<=2 || !(a&1)) return a==2;
    return !!(is[a>>4] & (1 << ((a >> 1) & 7)));
}