Crible d'Eratosthène et autres petits progs en C

[Membre supprimé 1]

Bonjour j'ai fait le crible d'Eratosthène mais j'aurai voulu savoir si il y avait moyen de réduire la complexité de l'algo ? Je pense pas qu'il soit très optimisé :/

Existe-il par hasard une version récursive ?

Merci si vous pouvez m'aider

[cpp]#include <stdio.h>
#define N 100


void statique()
{int nbre=2, i, test=1, cpt=0;
printf("\n");
while ( nbre<=N )
{ for (i=2 ; i<nbre ; i++)
{ if (nbre % i == 0) { test = 0; }
}
if (test) { printf("%d\n", nbre); cpt++;}
nbre++;
test = 1;
}
printf("\n%d nombres premiers au total\n", cpt);
}


void dynamique
{ int nbre=2, i, test=1, cpt=0;
printf("\n");
while ( nbre<=n )
{ for (i=2 ; i<nbre ; i++)
{ if (nbre % i == 0) { test = 0; }
}
if (test) { printf("%d\n", nbre); cpt++;}
nbre++;
test = 1;
}
printf("\n%d nombres premiers au total\n", cpt);
}


int main()
{ int choix, n;
while (1)
{ printf("\n1 Crible statique (n = %d)\n2 Crible dynamique\n3 Quit\n", N);
scanf("%d", &choix);
switch(choix)
{case 1 : statique(); break;
case 2 : printf("\nn = ? ");
scanf("%d", &n);
dynamique; break;
default : return 0;
}
}
}[/cpp]

 

[KangOl]

pourquoi tu as deux fonctions ?

 

[Membre supprimé 1]

[citation=3870,1][nom]kangol a écrit[/nom]pourquoi tu as deux fonctions ?

[/citation]
non mais ca ct dans l'énnoncé ... fallait faire une fct statique avec n=100 et une dynamique avec n en argument ... je sais ca sert à rien mais ct demandé [:spamafote]

Mais au niveau des 2 fonctions (c'est les memes de tte facon) l'algo doit certainement etre largement optimisable je pense ?

 

[thrips]

Pourquoi tu ne prends pas la même fonction mais que tu rajoute une valeur par défaut si aucune n'est choisie ?
[cpp]void dynamique(n=100)
{ int nbre=2, i, test=1, cpt=0;
printf("\n");
while ( nbre<=n )
{ for (i=2 ; i<nbre ; i++)
{ if (nbre % i == 0) { test = 0; }
}
if (test) { printf("%d\n", nbre); cpt++;}
nbre++;
test = 1;
}
printf("\n%d nombres premiers au total\n", cpt);
}
[/cpp]

 

[Membre supprimé 1]

[citation=3872,1][nom]ThripS a écrit[/nom]Pourquoi tu ne prends pas la même fonction mais que tu rajoute une valeur par défaut si aucune n'est choisie ?
[cpp]void dynamique(n=100)
{ int nbre=2, i, test=1, cpt=0;
printf("\n");
while ( nbre<=n )
{ for (i=2 ; i<nbre ; i++)
{ if (nbre % i == 0) { test = 0; }
}
if (test) { printf("%d\n", nbre); cpt++;}
nbre++;
test = 1;
}
printf("\n%d nombres premiers au total\n", cpt);
}
[/cpp]
[/citation]

Euh oui j'ai pas dit qu'on peut pas faire mieux pour les 2 fonctions mais précisement ce que j'aimerai améliorer c'est la complexité de l'algo notament cette ligne là qui doit etre optimisable : (puisque ya pas besoin d'aller juska nbre-1 normalement

[cpp]for (i=2 ; i<nbre ; i++)
{ if (nbre % i == 0) { test = 0; }
}
[/cpp]

 

[KangOl]

tu peu aller jusqu'a nbre/2 normalement...

 

[Membre supprimé 1]

[citation=3874,1][nom]kangol a écrit[/nom]tu peu aller jusqu'a nbre/2 normalement...
[/citation]
Ouais mais non puisque si par exemple nbre = 51 alors 51/2 = 25 et il trouverai 25 * 2 = nbre et il le classerait pas comme un nbre premier
faut mettre (nbre/2) + 1 non?

 

[nicoprog]

pour chercher un nombre premier tu n'a besoin d'aller qu'a la racine carré du nombre

 

[KangOl]

[citation=3877,1][nom]Zipo a écrit[/nom]
Ouais mais non puisque si par exemple nbre = 51 alors 51/2 = 25 et il trouverai 25 * 2 = nbre et il le classerait pas comme un nbre premier
faut mettre (nbre/2) + 1 non?
[/citation]
parce que pour toi 25*2 donne 51 :heink:

 

[chrisbk]

[citation=3880,1][nom]kangol a écrit[/nom]
parce que pour toi 25*2 donne 51 :heink:
[/citation]

non mais 51/2 = 25 en arithmetique entiere

 

[nicoprog]

51/2 = 25 + le reste de 1

 

[Membre supprimé 1]

[citation=3880,1][nom]kangol a écrit[/nom]
parce que pour toi 25*2 donne 51 :heink:
[/citation]
Ou t'as vu que j'ai dis que 25*2 = 51 ?
J'ai simplement dis que 51 / 2 = 25 (51 div 2 ...)
C'est du C hein

 

[Membre supprimé 1]

[citation=3879,1][nom]nicoprog a écrit[/nom]pour chercher un nombre premier tu n'a besoin d'aller qu'a la racine carré du nombre
[/citation]
Mon prof m'a dit d'aller juska sqrt(nbre+1)

 

[nicoprog]

je pense qu'il faut tester tous les nombres entiers < sqrt(nombre)
car au dessus on a deja testé et sqrt(nombre) se multiplie forcement par lui meme (par définition)

 

[Mossieur Propre]

moi, je l'ai fait en lisp y'a 4 jours [:dawa]

 

[Membre supprimé 1]

[citation=3890,1][nom]nicoprog a écrit[/nom]je pense qu'il faut tester tous les nombres entiers < sqrt(nombre)
car au dessus on a deja testé et sqrt(nombre) se multiplie forcement par lui meme (par définition)
[/citation]
Ouais je pense aussi

 

[nicoprog]

moi une fois j'avais fait un programme en C qui cherchait tous les nombres premiers jusqu'à 2 milliards et qui les enregistre dans un fichier texte, le seul probleme c'est que j'ai jamais réussit a voir le résultat car le fichier faisait 1Go ! lol

 

[Membre supprimé 1]

[cpp]
int prec(int x, int n)
{if (n==0) return 1;
else {
if (n % 2) return x * (prec(x, n/2) * prec(x, n/2));
else return prec(x, n/2) * prec(x, n/2);
}
}

int evaluerpoly(poly *p, int x)
{int i, s=0;
for (i=0 ; i <= (*p).deg ; i++)
{ s = s + (*p).coef * prec(x, i);
}
return s;
}
[/cpp]

Salut, ci dessus j'ai écris la fct evaluerpoly qui renvoie le résultat de l'évaluation du polynome p par l'entier x, elle fait appel à la fct prec qui calcule c^i récursivement.

Mais j'aimerai en fait une seule fct "evaluerpoly" qui calcule le résultat récursivement, vous avez une idée de comment s'y prendre ?
Merci d'avance !