/* crible.c * gcc -O2 -o crible crible.c */ #include #define MAX 500000 #define IMAX (MAX +31) >> 5 long crible[IMAX]; int max; #define isprime(z) ((crible[(z)>>5] & (1<<((z) & 31)))==0) void crible_init() { int i, j; max = MAX; /* tableau de MAX/32 entiers longs (32 bits) */ /* initialisation à 000...0 des entiers */ /* On marque comme non premiers les multiples de j à partir de j*j mult de 2 en partant de 4 : 4 6 8 10 12 14 16 ... 3 9 : 9 12 15 5 25 : 7 49 : */ j = 2; do { for (i = j * j; i < max; i += j) { crible[i >> 5] |= (1 << (i & 31)); } /* on passe à l'entier premier suivant (non marqué) */ while ((crible[++j >> 5] & (1 << (j & 31))) != 0); } while (j * j < max); } void affiche () { int i, cur = 2, rg=0; printf("int diff[] = {"); for(i=3;i