Corrigé de l'Exercice 1 du TD3

• Boucle 1:

    crible[0]=false;
    crible[1]=false;
    for(i = 2 ; i <= n ; i++) if(crible[i])
      for(j = 2*i ; j <= n ; j += i) crible[j]=false;
  

  Ici, la complexité est la somme de n/i pour tous les nombres i tels que crible[i] est true (donc pour tous les nombres premiers). Sachant que la somme de l'inverse des nombres premiers inférieurs à n est O(log log n), la complexité est en O(n.log log n).

• Boucle 2:

    crible[0]=false;
    crible[1]=false;
    for(i = 2 ; i <= n ; i++)
      for(j = 2*i ; j <= n ; j += i) crible[j]=false;
  

  La complexité est la somme de n/i pour tous les nombres i. Sachant que la somme de l'inverse des nombres inférieurs à n est O(log n), la complexité est en O(n.log n).

• Boucle 3:

    crible[0]=false;
    crible[1]=false;
    for(i = 2 ; i <= n ; i++) if(crible[i])
      for(j = i+1 ; j <= n ; j++) if((j%i) == 0)
        crible[j]=false;
  

  La complexité est la somme de n-i pour tous les nombres i. Sachant que le nombre de nombres premiers inférieurs à n est O(n/log n), la complexité est en $O(n2/log\; n)$.

• Boucle 4:

    crible[0]=false;
    crible[1]=false;
    for(i = 2 ; i <= n ; i++)
      for(j = 2 ; j < i; j++) if((i%j) == 0)
        crible[i]=false;
  

  La complexité est la somme de i pour tous les nombres i. La complexité est donc en $O(n2)$.

• Boucle 5:

    crible[0]=false;
    crible[1]=false;
    for(i = 2 ; i <= n ; i++) {
      k = (int) Math.sqrt(i); // racine carree de i
      for(j = 2 ; j <= k ; j++)
        if((i%j) == 0) crible[i]=false;
    }
  

  La complexité est la somme de sqrt(i) pour tous les nombres i. La complexité est donc en $O(n3/2)$.

Rappel de l'énoncé

On cherche à former la liste des nombres premiers inférieurs ou égaux à n. (Voir exercice 1 du TP2 et son corrigé.) On suppose que l'on a un tableau crible de boolean de n+1 éléments ainsi que des varirables d'entiers i, j, ... Au départ, tous les termes de crible sont initialisés à true. On considère les boucles suivantes

boucle 1:
  crible[0]=false;
  crible[1]=false;
  for(i = 2 ; i <= n ; i++) if(crible[i])
    for(j = 2*i ; j <= n ; j += i) crible[j]=false;

boucle 2:
  crible[0]=false;
  crible[1]=false;
  for(i = 2 ; i <= n ; i++)
    for(j = 2*i ; j <= n ; j += i) crible[j]=false;

boucle 3:
  crible[0]=false;
  crible[1]=false;
  for(i = 2 ; i <= n ; i++) if(crible[i])
    for(j = i+1 ; j <= n ; j++) if((j%i) == 0)
      crible[j]=false;

boucle 4:
  crible[0]=false;
  crible[1]=false;
  for(i = 2 ; i <= n ; i++)
    for(j = 2 ; j < i; j++) if((i%j) == 0)
      crible[i]=false;

boucle 5:
  crible[0]=false;
  crible[1]=false;
  for(i = 2 ; i <= n ; i++) {
    k = (int) Math.sqrt(i); // racine carree de i
    for(j = 2 ; j <= k ; j++)
      if((i%j) == 0) crible[i]=false;
  }

A la fin de ces cinq boucles, crible[i] indique si i est premier ou nom. Quelle est la complexité de ces algorithmes?