#include #include #include "memoire.h" #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 = memoire_allouer((n + 1) * sizeof(int)); int i; int npremiers = 0; int *premiers = memoire_allouer((n - 1) * sizeof(int)); 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; } memoire_liberer(t); *p_tpremiers = memoire_reallouer(premiers, npremiers * sizeof(int)); return npremiers; }