Session Nombres Premiers

ouvert a tous

<< 1 2

Anonyme

20 mai 2006 à 12:04:29

Voici ma solution, ça ressemble pas mal au code de kabuto_fr :
Secret (cliquez pour afficher)

/* premier.c

By louisclem. */

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

void premiers(int max);

int
main(int argc, char *argv[])
{
int max;
if (argc != 2)
return (1);
max = atoi(argv[1]);
if (max <= 0)
return (1);
premiers(max);
return (0);
}

void
premiers(int max)
{
unsigned long int i, j, max_div;
int div = 0;

for (i = 1; i <= max; ++i, div = 0) {
max_div = sqrt(i);
for (j = 2; j <= max_div; ++j) {
if (!(i % j)) {
div = 1;
break;
}
}
if (!div)
printf("%d\n", i);
}
}

L'avantage, c'est surtout qu'il peut afficher les nombres un par un à la suite. Si j'ai le temps, ça serait pas mal d'essayer de faire un truc qui puisse se mettre en pause en stockant son état dans un fichier texte puis en le ressortant.

J'ai testé le programme de bluestorm aussi, et j'y ai trouvé une petite erreurs qui fait sans doute consommer plus de mémoire : pour crible tu alloues taille * sizeof(int) alors qu'il contient des char donc taille * sizeof(char) sinon tu occupes 4 fois plus de mémoire

Iltharion

20 mai 2006 à 13:11:53

Citation : Pierre89

Il parait que la CIA ou le FBI (je sais plus) achète les nombres premiers au-delà de 10 puissance jeSaisPlusCombien pour du cryptage !
Mais rêver pas quand même ils ont des ordis plus puissant que vous, c'était juste pour l'anecdote !

C'est la NSA qui rachete les nombres premiers de 10^100 ca rend le craquage en temps reel impossible des clefs mais pas celui anticipée avec un temps de calcul de 15ans.

bluestorm

20 mai 2006 à 15:02:57

louisclem, j'avais déja corrigé cette erreur dans la nouvelle version, qui va bientôt sortir

Un conseil : Faites vos programmes :
- sans vous soucier de mesurer le temps, il vaut mieux faire ça en externe
- sans vous soucier d'écrire dans un fichier (ou pas du tout), il vaut mieux faire ça en externe
- sans afficher plus que nécessaire (le "Combien de machin pouet ?" du début est tout à fait inutile)

mrdus

20 mai 2006 à 16:08:56

heu vous en trouvez cb vous jusqu'à 1 million ?

edit : c bon j'ai trouvé
http://villemin.gerard.free.fr/Wwwgvmm/Premier/quantiPi.htm#Top

medkarim

20 mai 2006 à 21:08:53

Salut tous le monde

!!

En fait ,j'ai oublié de poster ma solution a moi :euh:

,
le code est vraiment hyper simple :lol:

:

Secret (cliquez pour afficher)

#include <stdio.h>
#include <stdlib.h>

int main(void) {
int n,nombreMaxi = 0;
printf("Entrez le nombre Maxi :\n");
scanf("%ld", &nombreMaxi);
printf("2\n");
for (n = 3; n <= nombreMaxi; n+=2) {
int i;
for (i = 2; i*i <= n; i++) if (!(n%i)) break;
if (i*i > n) printf("%d\n", n);
}
printf("\n");
system("PAUSE");
}

Ma solution représente une faible complexité, surtout coté RAM, il ne consomme que 740 Ko

Il reste bien sur a améliorer le code....

.

Merci .

bluestorm

21 mai 2006 à 12:12:43

Bon, voilà mon code actuel :
Secret (cliquez pour afficher)

#include <stdlib.h>
#include <stdio.h>
#include <math.h>

#define VAL(ind) (2*ind+1)
#define IND(val) (val/2)

int cribler(char crible[], int taille) {
int i, j, sqr;
sqr = sqrt(2*taille);
for (i = 1; i <= sqr; ++i)
if (crible[i] == 0) {
for (j = IND(3*VAL(i)); j < taille; j += VAL(i))
crible[j] = 1;
}
}

int main(void)
{
int i, nb_max, taille;
unsigned char *crible;
scanf("%d", &nb_max);
taille = nb_max / 2;
crible = calloc(taille, sizeof(unsigned char));

cribler(crible, taille);

printf("2\n");
for (i = 1; i < taille; ++i)
if (crible[i] == 0)
printf("%d\n", VAL(i));

free(crible);

return 0;
}

Pour les bench, j'ai regardé un peu, tous les algo qui n'utilisent pas de crible sont beaucoup, beaucoup (sur un million, c'est un facteur 10 environ) lents que les autres (c'est à dire moi et maminova, pour ce que j'ai tenté).

Le code de maminova est plus efficace (il triche, il a des bitset C++), donc à algorithme égaux il me bat (de 30% environ), mais ma nouvelle version contient pas mal d'améliorations, et je peux vous dire que je tue tout le monde pour l'instant

je suis en train de bosser sur la consommation de mémoire, je sortirai une nouvelle version qui règle le problème un de ces jours.

TheWall

21 mai 2006 à 13:59:51

J' essais de quelque jour de mettre au point mon algorithme utisant le crible, mais j' ai quelque difficulter , plus de nouvelle au prochain numero !!

Edit : Desoler pas taper pour la faute !!

bluestorm

21 mai 2006 à 14:01:00

algoriiiiiiiiiiiiiiiiiiiiiiiiiithme.

Léreldarion

21 mai 2006 à 17:55:34

j'essaie actuellement de programmer un algorithme utilisant le test de primalité de Rabin-Miller, un type de test d'un principe différent du crible et qui supplante le crible pour les grands nombres (dixit livre de math) si il est bien programmé.

EDIT : finalement il fonctionne mais a cause de la limititaion de taille des variables, il ne peut aller au dela de 1000000 (apres il y a des erreurs liées aux limitations des variables, et il se trompe).

Karaziox

22 mai 2006 à 22:54:48

Mon prog calcule les nombres premier a partir de 5 000 000 (5 million>) en 23 secondes

Pour ce qui est de la limitatino de var deja utiliser des unsigned

et sinon j'ai entendu parler de champs de bits du genre plus de bits pour une var (comme un int en 126 bits). Si je ne me trompe pas ca augmente la taille de stokage de la variable non?

P.S. Le 23 secondes correspondent seulement a la recherche des nombres donc l'allocation et l'affichage ne sont pas compris

Edit: 46 secondes au total avec affichage et allocation

(pour 5 million)

bluestorm

22 mai 2006 à 23:08:44

Hum, pour 5 millions, en redirgeant l'affichage vers un fichier, tout compris, je fais ça en 0.253 s (mais je prend 5 Mo de mémoire vive environ)

Karaziox

23 mai 2006 à 0:03:05

Ba moi aussi je prend 5 Mo de RAM (enfin jcroi :P) ... Mais bon jai fait ca a la vite et pas optimisé 1 brin

Poischack

23 mai 2006 à 14:03:29

Pourquoi rediriger vers un fichier ? rediriger vers /dev/null serais plus logique. (bien qu'avec le systeme de cache les accès I/O devrais pas intervenir pour de si petits trucs))

bluestorm

23 mai 2006 à 15:12:24

Bah je redirige vers /dev/null en général, mais comme des gens écrivent dans des fichiers depuis leur code C (ils savent pas rediriger visiblement), /dev/null c'est moins honnête quand je veux comparer les temps.

icepower3125

31 mai 2006 à 16:19:31

Hello!
j'ai fais un programme qui utilise le crible d'Erathostène et il met 4s pour aller jusque à 1 milion mais je ne vois pas pourquoi UTILISER LE TEMPS

<< 1 2