[Concours de programmation] Première épreuve.

Le problème:

Le but du problème est de calculer tous les nombres premiers compris strictement entre deux bornes.
Rappel: un nombre premier est un nombre qui est divisible par exactement deux naturels distincts (1 et lui-même).
Rappel: les premiers nombres premiers sont 2,3,5,7,11,13,17,19,23,29,31,...
Attention: 1 n'est pas un nombre premier !

Exemple: si les bornes sont 5 et 20, le programme doit retourner 7,11,13,17,19.

Entrée (input):

Un fichier texte contenant deux nombres naturels dans l'ordre croissant, séparés par un espace. Il n'y a pas de limite de taille sur ces nombres.
Exemple 1: 0 100
Exemple 2: 2000 30000
Exemple 3: 987654321012345678901234567890 987654321012345678902345678900

Sortie (output):

Un fichier texte contenant le nombre de nombres premiers trouvés suivit de la liste de ces nombres.
Exemple: Pour un fichier d'entrée "5 32" il faut un fichier de sortie "8 7 11 13 17 19 23 29 31"

Objectif:

Rapidité d'exécution !

Langages autorisés:

C/C++
Java
Python
Pascal


Dead Line:

Le code source du programme doit être remis à Julien ou moi-même pour le 20 avril au plus tard.

On a le droit de combiner les langages ? (Je n'ai pas d'exemple mais pourquoi pas...) Et pourquoi restreindre les langages ?

Sinon, pas de recommandations sur la mesure du temps d'exécution ?

J'espère que j'aurais le temps de m'y mettre parce que ça peut être intéressant mais j'ai tellement de projets en cours qu'il faudrait que j'en finisse un peu avant de commencer d'autres choses...

Julien a écrit:Et pourquoi restreindre les langages ?

Peut être parce que les language comme mathématica sont trop specialisé en matiére
et aussi peut être parce que ce concours et un deal entre ces languages(les plus célébre)

Et aussi parce que pour tester un code matlab ou mathématica, la rapidité dépendra de la version. Et les version récentes ne sont pas gratuites !

Pour ce qui est de la gestion du temps, je propose le schéma suivant:

Début du timer
Chargement des données
Calculs
Ecriture des résultats.
Fin du timer

Les input-output étant des opérations lentes dépendant principalement de la configuration de la machine, je pense qu'il ne sont pas importants.

OK, donc tu veux calculer que le temps de calcul. Ca marche.

Sinon, j'ai fait une première version en C avec la méthode du crible d'Erathostène. Inutile de dire que c'est la méthode la moins performante ! ^^

Pour trouver les nombres premiers entre n'importe quelle borne inférieure à 40 000 et 40 000, ça prend déjà plus de 6 secondes chez moi...
49 secondes pour les nombres premiers inférieurs à 100 000. :p

Tout ça pour dire que si tu veux porteuris, tu peux déjà faire cette méthode. Elle est simple à mettre en oeuvre.

Après, faut chercher les algorithmes pour améliorer.

Julien a écrit:
49 secondes pour les nombres premiers inférieurs à 100 000. :p

Juste une précision : en rajoutant la bonne ligne qu'il faut, je passe de 49 secondes à moins d'une demi-seconde...

En fait, ca peut restreindre les possibilités... Donc c'est pas génial.

Début du timer avant la lecture du fichier, fin du timer après l'écriture du fichier.

Bon ben alors dans ce cas je ferai avec la commande time. Ca m'arrange !

Petite adaptation en fonction des problèmes que l'on peut rencontrer.

- Les valeurs du fichier final peuvent être séparées par plus d'un espace si nécessaire (sinon ça risque d'exploser la ram sur les petites config (et même sur les grosses)).

- Je pense que pour ne pas pénaliser les config lentes, il serait pas mal de faire le calcul de la durée de l'algo en supprimant l'écriture dans le fichier. Cette écriture n'est là que pour vérifier qu'il n'y a pas de triche/erreurs de toutes façons. (en la mettant en commentaire pour le test de temps). D'autant plus que ça change beaucoup de chose, ce qui rend difficilement visibles les petites optimisations de l'algo en lui-même. (j'ai un différence d'un facteur 10 chez moi).

Duche a écrit:- Les valeurs du fichier final peuvent être séparées par plus d'un espace si nécessaire (sinon ça risque d'exploser la ram sur les petites config (et même sur les grosses)).

C'est quoi l'avantage de mettre plusieurs espaces ?

De ne pas devoir tout stocker en mémoire ram.
Puisque la première valeur du fichier doit être le nombre de nombres premiers trouvés.
Il suffit de laisser un peu de place (pas trop, pas trop peu, à vous de choisir les critères) et puis l'écrire après.

Ok... je n'ai pas eu de problème encore. C'est en affichant combien de nombres que ça te demande trop de ressources ? Et t'as combien de RAM ?

J'ai 1Go de RAM.
En fait comme il faut fournir le nombre de valeurs trouvées avant ces valeurs, il faut stocker les valeurs trouvées en RAM ou faire un transfert de fichier (lourd).

Pour le moment, j'ai mis au point un algo qui gère bien les nombres jusqu'à 100 chiffres (en base 10). Bien évidemment, le calcul sur des nombres aussi grands est infaisable pour des petits ordinateurs comme les notres...

Voila pour le moment les chiffres que j'ai (l'ordi tournait avec beaucoup d'applications, mais je ne pense pas que le laisser avec seulement le programme pourrait changer beaucoup de choses...)

1 10000 -> Duree de la recherche : 0.113260 sec.
1 40000 -> Duree de la recherche : 0.754984 sec.
1 100000 -> Duree de la recherche : 2.551853 sec.
1 200000 -> Duree de la recherche : 6.689810 sec.
1 300000 -> Duree de la recherche : 11.660389 sec.
1 400000 -> Duree de la recherche : 17.435228 sec.
1 500000 -> Duree de la recherche : 24.039731 sec.
1 1000000 -> Duree de la recherche : 63.384426 sec.
1 10000000 -> Duree de la recherche : 1787.598792 sec.
1000000000000000 1000000000010000 -> Duree de la recherche : 17993.159675 sec.


Etant donné que certains types (du moins en C++) peuvent gérer les nombres jusqu'à 2^64, je me demande s'il ne serait pas judicieux d'abandonner l'idée de la taille illimitée.
Cela dit, il est intéressant de développer les opérations de bases pour des grands nombres, mais ça reste assez indépendant...
Je propose de tester également l'algo avec des types allant jusque 2^64. (2^32 est quand meme un peu faible)

Edit:
J'ai implémenté le même algo pour la recherche des nombres premiers, mais avec le type entier de 64 bits.
La différence est éloquente
1 10000 -> Duree de la recherche : 0.002130 sec.
1 40000 -> Duree de la recherche : 0.011390 sec.
1 100000 -> Duree de la recherche : 0.022692 sec.
1 200000 -> Duree de la recherche : 0.064430 sec.
1 300000 -> Duree de la recherche : 0.099417 sec.
1 400000 -> Duree de la recherche : 0.132191 sec.
1 500000 -> Duree de la recherche : 0.170892 sec.
1 1000000 -> Duree de la recherche : 0.426916 sec.
1 10000000 -> Duree de la recherche : 9.467974 sec.
1000000000000000 1000000000010000 -> Duree de la recherche : 53.533033 sec.

Edit edit: Je me suis amusé avec quelques nombres encore plus grands, mais je ne peux pas aller plus haut avec ce type:
10000000000000000 10000000000000100 -> Duree de la recherche : 2.507479 sec.
100000000000000000 100000000000000100 -> Duree de la recherche : 12.448282 sec.
1000000000000000000 1000000000000000100 -> Duree de la recherche : 22.885113 sec.
10000000000000000000 10000000000000000100 -> Duree de la recherche : 114.811577 sec.

Juste une question : quand tu mets une borne inférieure égale à 1000000 par exemple, c'est juste que t'affiches les résultats juste à partir de ce nombre et que ton algo fait tout le travail pour les nombres inférieurs ou pas ?

Non non, l'algo commence à la borne inférieure.

OK, j'ai plus qu'à trouver comment faire alors. ^^

Tu utilisais les nombres premiers précédemment trouvés pour tester la primalité ?

Oui, je fais avec la méthode du crible d'Eratosthène pour le moment.

Ok, moi je fais avec un test de primalité.