#include #include #include "premiers.h" /* Calcul les nombres premiers inférieurs ou égaux à n par le crible d'Eratosthène. Renvoie le nombre de nombres premiers obtenus et met dans p_tpremiers l'adresse d'un tableau contenant ces nombres. */ int premiers_inferieurs(int n, int ** p_tpremiers) { /* Pour simplifier le code, on réserve t[0] et t[1] pour rien */ int *t = malloc((n + 1) * sizeof(int)); int i; int npremiers = 0; int *premiers = malloc((n - 1) * sizeof(int)); assert(t != NULL); assert(premiers != NULL); for (i = 0; i <= n; i++) t[i] = 1; for (i = 2; i <= n; i++) if (t[i]) { /* i est premier et on doit éliminer ses multiples. */ int j; premiers[npremiers ++] = i; for (j = i; j * i <= n; j++) t[j * i] = 0; } free(t); *p_tpremiers = realloc(premiers, npremiers * sizeof(int)); return npremiers; }