Partage

Session Nombres Premiers

ouvert a tous

1 2 >>

El Tonio

17 mai 2006 à 19:39:15

Bluestorm a ecrait dons un topic voisin :

Citation : bluestorm

Fais un programme qui affiche rapidement tous les nombres premiers entre 0 et un million, par exemple.

D'ou l'idée de creer une session ouverte au plus grand nombre.

L'interet de ce petit exercice est qu'il peut etre realisé tres tot dans l'apprentissage du C, et donc ets ouvert au plus grand nombre.

Cahier des charges :

EDIt : j'allais oublier : le programme sera en console, et ecrira tous les nombres premiers qu'il toruve jusqu'a nombre maximum. Plutot important comme regle

Le programme n'exedera pas 1 Mo (je sias la limite est large, mais elle a pour seul but que personne ne fasse calculer son programme, puis en ecrive un autre avec que des printf)
Le programme devra CALCULER.
Le programme laissera le choix en debut de calcul du nombre jusqu'au quel il doit calculer les nombres premiers, jusuqu'a une limite de 2 147 483 647 (un long ou un int)

Structure du programme :

int main();
{
int nombreMaxi = 0;
printf("Entrez le nombre Maxi.\n")
scanf("%d", &nombreMaxi);
Uint32 temps = 0;
temps = SDL_GetTicks

// declaration de vos variables APRES SDL_GetTicks

// votre code, avec ou sans appel de fonctions

printf("Temps : %d", temps);
getchar();
return EXIT_SUCCESS;
}

Evaluation :

Tout d'abord il n'ya rien a gagné si ce n'ets votre nom sur la plus haute marche du podium.

Tous les programmes dans lesuqels le cahier des charges est respecté seront executé le meme jour, sans modification de l'evironnement sur lequel il tourneront (a savoir le mien

). Le critere de jugement est bien entendu le temps que met le programme pour effectuer la tache demandée). Pour que je puisse verifier le cahier des charges veuillez me faire passer vos sources aussi. Les liens vers les programmes devront etre envoyés en mp, et posté ici (vous pouyvez poster une version sans les sources ici).
Vous n'avez pas besoin de fournir SDL.dll dans votre fichier zip. Si vous avez un probleme pour uploader votre programme, contactez moi.

Si toutefois, vous vouliez connaitre le score de votre programme sur 1 000 000 et sur mon environnement avant la date imposée, contactez moi par mp, j'executerais votre programme et en afficherai le resultat. Le jour de l'evaluation, le nombre maxi sera tire au hasard.

Sur ce, j'espere que ce topic sera bien accepté,

Bonne chance a tous.

El Tonio

Knarf2

17 mai 2006 à 20:39:37

Mouais, je vois pas l'intéret d'utiliser la SDL ici.
- Fait passer le nombre max dans les aguments d'appel de main (argv)
- Pour le temps,

./time tonprog

Anonyme

17 mai 2006 à 20:43:30

la SDL --> Chronométrer proprement.

Sinon je participerais peut être.

Duarna

Pierre89

17 mai 2006 à 21:06:13

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 !

TheWall

17 mai 2006 à 21:43:52

Non c' est la societer qui a mis au point le cryptage RSA , et il achete le Facteur premiers d' un nombre , mais c' est dernier necessite environ 100 ans de calcul voire beaucoup plus sur un ordinateur personelle.

Sinon moi je fais

En faite c' est a celui qui trouvera le meilleur alogorythme

maminova77

17 mai 2006 à 21:48:10

si tu veux des très grand nombre premier, test avec les long long int...

Pierre89

17 mai 2006 à 22:13:36

En fait la technique qui m'apparaît la plus simple est d'imbriquer deux boucles for : dans l'une on incrémente i, et dans l'autre on teste si i è divisible par tous le nombre en dessous de i grâce à un j qu'on incrémentera aussi, enfin à l'intérieur de la boucle fo qui est a l'intérieur de la boucle for (ça va vous me suivez ?) on mais une condition if qui mais un booléens fait sortir de la boulce intérieur par un break; sinon on affiche le nombre.
Dites moi si cela ne marche pas !

Orochi

17 mai 2006 à 22:16:41

pour aller plus vite, tu ne test pas les multiples de 2 et tu test chaques nombres avec les tous les nombres premiers précedents (enfin c'est comme ca que je ferai, mais peut etre qu'il existe plus rapide)

bluestorm

17 mai 2006 à 23:52:15

Pour le temps, je préfère utiliser la commande linux qui fait ça, est plus fiable, et rajoute pas une initialisation SDL qui est plus lente que tout le reste du code réuni

medkarim

18 mai 2006 à 0:11:38

Salut tous le monde

!!

J'ai trouvé la solution :lol:

:
Voici le lien pour telecharger le fichier :

http://med-karim.ifrance.com/

Les deux programmes fonctionnent bien sur , meme avec la limite : 2 147 483 647 .
et je pense qu'il peut allez plus loin .
La taille est de 16 Ko seulement

....

Merci .

bluestorm

18 mai 2006 à 0:16:53

Hum, et le temps environ ?

(16 Ko de code source ? C'est un peu étonnant franchement...)

medkarim

18 mai 2006 à 0:19:18

Salut

,

Le temps d'execution est d'environ 4s pour le nombre 1000000,
et pour le max ca prends du temps un peu , c'est quand meme un grand nombre ....

Merci .

Poischack

18 mai 2006 à 8:39:54

Il peut-être interressant de donner un lien pour expliquer ce qu'est un nombre premier: http://fr.wikipedia.org/wiki/Nombre_premier .

seb13

18 mai 2006 à 10:51:15

Pour le temps cela sert à rien d'utiliser la SDL:

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

int main(int argc, char *argv[])
{

time_t timestamp1;
int duree;

timestamp1 = time (NULL);

// calcul du nombre premier

duree = time(NULL) - timestamp1;
printf("%ld", duree);
}

mrdus

18 mai 2006 à 11:06:37

ha merci seb13 me rappelais plus comment on faisait avec time.h, cool

baptou

18 mai 2006 à 13:58:58

Si vous voulez savoir voila le plus grand nombre premier que j'ai trouver avec un int

2 147 483 629

pour un int maximum de 2 147 483 647.

azerty9

18 mai 2006 à 17:51:01

un si grand nombre difficilement verifiable.
j'ai une idee de comment faire une partie du code mais apre sje sais pas trop.

El Tonio

18 mai 2006 à 18:18:43

Citation : seb13

Pour le temps cela sert à rien d'utiliser la SDL:

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

int main(int argc, char *argv[])
{

time_t timestamp1;
int duree;

timestamp1 = time (NULL);

// calcul du nombre premier

duree = time(NULL) - timestamp1;
printf("%ld", duree);
}

je rejoute dans le prmeier post

florent28

19 mai 2006 à 11:50:32

Mon exécutable (windows pour le moment) est là : http://florent28.free.fr/C/NPremier.zip
Il fait 9ko.

Difficile de déterminer le temps d'exécution, car il varie énormément quand je teste avec 1000000 sur mon portable du boulot (P3 850). Je testerais dès que je peux chez moi.
Et de toute façon, les temps d'exécution ne sont valables que si exécutés sur le même pc. Et encore, on n'a une précision à la seconde, seulement, avec les fonctions time.h...

Pour 1000000 : 78498 nombres premiers trouvés.

edit : pendant la pause déjeuner, je vais lancer le programme avec le nombre maximal, histoire de voir combien il y en a

Edit 2 : la version qui inscrit tout dans un fichier est aussi en ligne. Elle est d'ailleurs plus rapide que la version qui affiche en console (pour 1000000, gain de 30% environ). http://florent28.free.fr/C/NPremier-fichier.zip

Natim

19 mai 2006 à 12:32:36

C'est simpa comme sujet !
Je vous code cela rapidement !
Sinon, pour le temps !
Personne ne sait comment avoir les milliseconde ?
J'ai entendu parler de GetTimeOfDay, mais je ne sais pas comment l'utiliser !

maminova77

19 mai 2006 à 13:19:20

Il existe une méthode simple qui utilise le crible d'Eratosthène :

Secret (cliquez pour afficher)

#include <iostream>
#include <bitset>

using namespace std;

int main( ){
const int N = 70;

bitset<N+1> b;
int i;
for(i=2;i<=N;i++)
b.set(i);
i=2;
while(i*i<=N) {
if(b.test(i)) {
int k=2*i;
while(k<=N) {
b.reset(k);
k+=i;
}
}
i++;
}
i=1;
while(i<=N) {
if(b.test(i)) {
cout << "i :" << i << " test : " << b.test(i) << endl;
}
i++;
}

}

seb13

19 mai 2006 à 14:11:04

Peut être que tu aurais pu laisser les gens chercher par eux même (même si personne n'est obligé de regarder la solution).

florent28

19 mai 2006 à 14:15:58

C'est simple à condition de connaître <bitset>

baptou

19 mai 2006 à 18:54:03

Citation : florent28

Pour 1000000 : 78498 nombres premiers trouvés.
http://florent28.free.fr/C/NPremier-fichier.zip

moi perso g trouve 99991 mais je me trompe peut être

Pourrait t on avoir un 3eme avis??

a dsl g me suis tromper je n'avais pas comprit la phrase moi c'est le plus grand que j'ai trouver dans l'intervale ]0;100000] dsl

bluestorm

19 mai 2006 à 21:09:08

Si vous voulez, envoyez moi vos code, je ferais un benchmark avec la commande time de linux, beaucoup plus pratique que les bidouilles dans le code source.

Voici le mien, perso :
Secret (cliquez pour afficher)

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

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

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

cribler(crible, taille);

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

return 0;
}

El Tonio

19 mai 2006 à 21:14:11

il faudrait le faire avec la SDL enb fait pour avoir un temps en ms, ce qui est bcp plus precis

bluestorm

19 mai 2006 à 22:01:54

Bah moi j'utilise l'utilitaire time, et j'ai le temps en ms, sans rien changer à mon programme.

Parce que la SDL, elle se charge, donc ça augmente la durée du programme. Pas terrible pour un truc sensé améliorer la précision.

Pour infos, sur mon PC je calcule les nombres premiers de 2 à 120 millions en 17 secondes (17.256 s sur une moyenne de 10 essais, précisément).
Je vais un peu moins vite que le code de maminova je pense, parce que, codant en C de base, je n'ai pas accès aux bitset.

kabuto_fr

20 mai 2006 à 5:32:54

Salut a tous,

Bluestorm ton programme est rapide, mais il a un gros inconvegent, il bouffe beaucoup de RAM.
17s pour 120millions, ca veut dire que pendant cd temps il prend 120MO de RAM.
J'ais tester avec 300millions, rien que l'allocation memoire dure plus de 2seconde.
Il est donc impossible de tester des tres grans nombre comme 2 147 483 647 equivalent a +de 2GO de RAM.

j'ai essayer le defis mais mon programme fait 16Ko et en plus il est super lent.

Secret (cliquez pour afficher)

int calculNombrePremier(const long limite)
{
long i,j,total = 0;
long nombrePremier =0;
printf("\n 2 ");

for (i = 3; i < limite; i+=2)
{
for (j = 2; j < i; j++)
{
if ((i%j) == 0)
{
nombrePremier = 0;
break;
}
else
nombrePremier = 1;

}
if (nombrePremier)
{
printf(" %ld ", i);
total++;
}
}

printf("\nIl y a %ld nombre premier.", total+1);

return EXIT_SUCCESS;
}

bluestorm

20 mai 2006 à 6:20:06

Oui il prend de la RAM, mais je suis en train d'étudier des solutions pour lui en faire manger moins

Léreldarion

20 mai 2006 à 7:28:12

Citation : kabuto_fr

Bluestorm ton programme est rapide, mais il a un gros inconvegent, il bouffe beaucoup de RAM.
17s pour 120millions, ca veut dire que pendant cd temps il prend 120MO de RAM.
J'ais tester avec 300millions, rien que l'allocation memoire dure plus de 2seconde.
Il est donc impossible de tester des tres grans nombre comme 2 147 483 647 equivalent a +de 2GO de RAM.

Ceci est la principale raison qui fait du crible d'ératosthène une méthode limitée, car si elle est rapide elle necessite beaucoup de mémoire pour stocker les nombres premiers (enfin bon ca ne devient problematique que pour des grands premiers, ou l'on utilise alors les tests probabilistes, celui de Rabbin-Miller par exemple).

PS : Je vais essayer

PS² : A partir d'une certaine vitesse de calcul ce n'est pas la vitesse d'affichage qui peut ralentir ?

1 2 >>