#include <stdio.h>
#include <stdlib.h>
#include <math.h>

/* Made by Michael Westergaard (c) 2000, you may use this program freely */

unsigned char *matrix;

unsigned char two[]={0,0x1,0,0x2,0,0x4,0,0x8,0,0x10,0,0x20,0,0x40,0,0x80};

int main(int argc, char **argv) {
    register int i,j,k;
    register int upto=atoi(argv[1]);
    register int max=((int)sqrt(upto))+1;
    matrix=new unsigned char[upto/16+1];
    for (i=3;i<=max;i+=2) {
        if ((!(matrix[i>>4] & two[i&0xf]))) {
            k=i<<1;
            j=i*i;
            while (j<=upto) {
                matrix[j>>4]|=two[j&0xf];
                j+=k;
            }
        }
    }
    printf("1\t2\n");
    j=2;
    for (i=3;i<=upto;i+=2) {
        if (!(matrix[i>>4] & two[i&0xf]))
            printf("%u\t%u\n",j++,i);
    }
    return 0;
}