Nombres premiers (RAM / Vitesse)

Bonsoir.

Voilà, j'aimerais créer un programme en C affichant le plus grand nombre premier inférieur ou égal au nombre rentré par l'utilisateur. Je voudrais également que ce programme soit à la fois rapide, et utilise peu de mémoire vive.

Voici deux programmes, le premier utilise le reste de la division euclidienne pour déterminer si le nombre est premier ou pas, n'utilise pas beaucoup de mémoire vive mais est assez lent (0.6s pour venir à bout de 1 million de nombres). Le deuxième utilise le crible d'Eratosthene et n'utilise que des additions (consomme énormement de mémoire) et est relativement rapide (0.036s pour 1 million de nombres).

Avec le modulo :

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
 
typedef enum
{False = 0, True = 1}
Bool;
 
int main()
{
    int n, la;
    int k = 1;
    int p = 500;
    Bool test = True;
 
for(n = 3; n <= p; n+=2)
{
    test = True;
    double fs = floor(sqrt(n));
    int j;
        for(j = 2; j <= fs; j++)
        {
            if(n % j == 0)
            {
                test = False;
                break;
            }
        }
        if(test)
        {
        k ++;
        la = n;
        }
}
    printf("%d\n", la);
    printf("\nParmi les %d premiers nombres, %d sont premiers.\n", p, k);
    return 0;
}

Avec le crible d'Eratosthene :

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
 
#define NB 1000000
 
typedef enum
{False = 0 , True = 1}
Bool;
 
const int p = NB;
Bool arr[NB] = {False};
 
int main() {
    int k = 0;
    int i, la;
    for (i = 2; i < p; i++)
    {
        if (!arr[i])
        {
            for (int m = i << 1; m < p; m += i)
            {
                arr[m] = True;
            }
 
            k++;
            la = i;
        }
    }
    printf("%d\n", la);
    printf("\nParmi les %d premiers nombres, %d sont premiers.\n", p, k);
    return 0;
}

Comment puis-je faire pour "combiner" les deux et avoir un programme à la fois rapide et qui consomme peu de mémoire (par exemple en utilisant tous les coeurs de mon processeur) ?
Merci pour votre aide.

<\EchoIsON>