Les n premiers nombres premiers

Expliques dans tes mots l'algorithme que tu veux utiliser. Je ne saisis pas ta logique ...

Tu testes des choses dans le tableau t alors qu'il n'est pas initialisé, entre autres.

On commence à 2 et on teste des diviseurs de 2 jusqu'à la racine carrée du nombre: j*j <= i

Ce n'est pas une bonne idé que de commencer avec c = -1. Commences avec c = 0 et incrémentes après l'assignation.

Bonjour,

l'algo, ce serait dans ce genre là:

fonction est_premier(n):
    si n <= 1
       retourner 0
    boucle for k de 2 à n
        si n modulo k == 0
            retourner 0
    retourner 1

boucle for k de 0 à n
    si est_premier(k)
        afficher k

L'énoncé de Otmar dit qu'il cherche les N premiers "nombres premiers".
La boucle suivante:
    while (t[n]==0)
était censée lui donner une limite, mais t[n] est hors range, donc c'est un comportement indéterminé.
Je suggérais:
    c = 0;
    while(c < n) {
        // blabla
        t[c++] = i;
    }

Je doute qu'il connaisse les fonctions.

Bonjour,

Comme le souligne PierrotLeFou, ton tableau n'est pas initialisé. Tu ne peux pas déclarer un tableau avec int tab[n] (déclaration statique) si n n'est pas connu à la compilation. Ici, n est au connu à l'exécution (quand l'utilisateur saisit la valeur de n) et donc il est nécessaire de faire une allocation dynamique (e.g. avec malloc, voir cet exemple).

Quelques recommandations

• Essaye respecter les conventions habituelles : un espace derrière les ponctuations (virgules, point virgules), un espace autour des opérateurs.
• Essaye de donner des noms habituels à tes variables : i, j, k pour des index entiers qu'on incrémente, n ou m pour des tailles.
• Essaye d'utiliser des types parlants : size_t pour des index et des tailles (entiers positifs).
• Essaye d'indenter ton code correctement.
• Essaye de décomposer ton code en fonction : cela améliorera significativement sa lisibilité.
• Il n'y a pas besoin d'écrire un espace avant un retour à la ligne.
• Tu peux réutiliser certaines variables. Par exemple la variable a (outre son nom peu parlant) pourrait très bien être remplacée par i ou j.
• Tu as oublié d'indiquer la valeur de retour de main (0 si tout va bien par convention, une valeur entre 1 et 255 identifiant un code d'erreur sinon).

Au niveau du code 

• La première boucle while est correcte mais un peu étrange. Il serait plus naturel de contrôler si le nombre premier que tu t'apprêtes à mémoriser est à l'index n ou pas.
• Le pseudo code que tu proposes pour tester si n est premier est incorrect, car tu dois tester au moins tous les nombres premiers compris entre 2 et racine(n)

Voici une correction préliminaire de ton code

void afficher_tableau(size_t * tab, size_t n) {
    printf("[");
    for (size_t i = 0; i < n; i++) {
        printf(" %zu", tab[i]);
    }
    printf(" ]");
}

bool est_premier(size_t k) {
    // NB: Il suffit de tester jusqu'à sqrt(k)
    for (size_t i = 2; i < k; i++) {
        if (k % i == 0) return false;
    }   
    return true;
}

int main()
{   
    size_t i = 0, // Index où l'on va stocker le prochain nombre premier
           k = 2, // Entier en cours de test
           n;     // Nombre de valeurs à générer

    printf("Hello !\n");
    printf("Combien de nombres premiers ? ");
    scanf("%d",&n);
    
    size_t * tab = malloc(sizeof(int) * n);
    if (!tab) {
        fprintf(stderr, "Erreur mémoire\n");
        return 1;
    }
        
    for (size_t i = 0; i < n; i++) {
        while(!est_premier(k)) {
            k++; 
        }
        tab[i] = k;
        k++;
    }
    printf("Les %zu premiers nombres premiers sont: \n ", n);
    afficher_tableau(tab, n);
    printf("\n");
    free(tab);
    return 0;
}

Exécution :

(mando@silk) (~) $ gcc toto.c && ./a.out  
Hello !
Combien de nombres premiers ? 10
Les 10 premiers nombres premiers sont:  
[ 2 3 5 7 11 13 17 19 23 29 ]

Améliorations

Note toutefois que la fonction est_premier que je t'ai indiqué peut (doit ?) être amélioré :

Il est inutile de vérifier tous les entiers entre 2 et n pour vérifier si n est premier : on peut s'arrêter à racine(n).

• Pour faire cette amélioration, il faut ajouter #include <math.h>, utiliser la fonction sqrt, et compiler en ajoutant l'option -lm pour lier le programme à la librarie maths (on teste ainsi seulement racine(k) valeurs au lieu de k):

gcc toto.c -lm && ./a.out

Dans le cas particulier de ton programme, tu peux faire bien mieux. Comme tu connais les nombres premiers calculés avant k, il serait dommage de ne pas les exploiter. On sait que si k n'est pas premier, il est forcément divisible par un des nombres premiers trouvés jusqu'ici ; et donc si aucun ne le divise, alors on a trouvé un nouveau nombre premier (on teste alors i valeurs au lieu de racine(k)).

• Pour faire cette amélioration, il faut passer tab et i en paramètre à la fonction est_premier.

Ces deux amélioration améliorent la complexité de ton algorithme. C'est une notion essentielle à avoir en tête en programmation pour écrire des programmes non seulement plus efficaces, mais aussi plus écologiques car moins énergivores.

Bonne chance

Otmar a utilisé des VLA dans son code, ce qui est tout a fait valide. (VLA = Variable Length Array)
Je ne crois pas qu'il soit rendu au stade des malloc.
C'est plus compliqué (pour un débutant) de tester contre les nombres premiers accumulés que les nombres (impairs si possible) inférieurs au nombre (ou sa racine carrée).

Si on prend pour acquis que 2 est premier, on pourrait ne considérer que les nombres impairs et les diviseurs potentiels impairs. On réduit déjà par un facteur de 4 le temps d'exécution, presque sans effort.

En complément, j'aimerais préciser ceci:
Quand on teste un nombre assez petit avec peu de diviseurs potentiels, c'est correct de faire:
    while(diviseur * diviseur <= nombre) ...
Si on teste un "seul" nombre relativement grand avec possiblement plusieurs diviseurs potentiels, il est préférable d'utiliser sqrt():

    racine = sqrt(nombre);
    while(diviseur <= racine) ...

Parce que sqrt() prend un certain temps à s'exécuter, mais pas tant que ça. Il converge habituellement en 5 ou 6 itérations.
Quelles sont les opérations pour chaque itération? Quelque chose du genre:

    r1 = (nombre/r0 + r0) / 2;

avec les tests de convergence.
Mais si on a une suite de nombre consécutifs, on remarquera que leur racine carrée entière est la même. Par exemple:
les nombres de 25 à 36 (exclus) ont 5 comme racine carrée entière. Donc 11 nombres dont 6 nombres impairs.
Quand on est rendu vers 900 millions, il y a environ 30000 nombres impairs avec la même racine carrée entière.
J'ai écrit le code suivant pour illustrer la méthode à suivre. Elle est basée sur le truc:
(n+1)^2 = n^2 + 2*n + 1

#include <stdio.h>
int main(void) {
    printf("Combien de nombres? ");
    int max;
    scanf("%d", &max);
    int premiers[max];
    premiers[0] = 2;
    premiers[1] = 3;   // Pour éviter de toujours tester le nombre 2.
    int c = 1;   // Compteur.
    int n = 1;
    int r = 1;   // (int) sqrt(3)
    int s = r+1;
    s *= s;   // Carré suivant, ici 4
    while(c < max) {
        n += 2;   // Nombres impairs (le premier est 3).
        if(n >= s) {
            r++;   // On augmente la racine carrée.
            s += 2*r + 1;   // On passe au carré suivant.
        }
        // J'utilise un pointeur et mes diviseurs sont les nombres premiers déjà accumulés.
        int *p = premiers+1;
        while(*p <= r)   if(n % *p == 0)   break;   else   p++;
        if(*p > r)   premiers[c++] = n;
    }
    for(int i = 0; i < c; i++)   printf("%d\n", premiers[i]);
    printf("Le dernier nombre est %d\n", premiers[c-1]);
}