NBRPREMS (recherche des nombres premiers)
Actions
Vote (4.5/5):
Informations
Auteur Author: Xavier Andréani
Type : Basic
Taille Size: 351 octets bytes
Mis en ligne Uploaded: 26/12/2009 - 16:48:29
Mis à jour Updated: 01/01/2012 - 10:49:07
Uploadeur Uploader: critor (Profil)
Téléchargements Downloads: 2144
Visibilité Visibility: Archive publique
Shortlink : http://ti-pla.net/a1529
Type : Basic
Taille Size: 351 octets bytes
Mis en ligne Uploaded: 26/12/2009 - 16:48:29
Mis à jour Updated: 01/01/2012 - 10:49:07
Uploadeur Uploader: critor (Profil)
Téléchargements Downloads: 2144
Visibilité Visibility: Archive publique
Shortlink : http://ti-pla.net/a1529
Description
NBRPREMS est un tout petit programme de recherche des nombres premiers.
La complexité reste exponentielle (il ne faut pas attendre de miracle), mais je l'ai optimisé le plus que j'ai pu en mettant le moins d'instructions possibles dans la boucle.
Il est basé sur la condition nécessaire et suffisante suivante:
"un nombre n est premier" si et seulement si "il est divisible par tous les nombres premiers inférieurs à racine de n"
Le programme construit donc pas ordre croissant une liste des nombres premiers, et s'en sert au fur et à mesure pour trouver de plus grands nombres premiers.
A tout moment, vous pouvez arrêter le programme en tapant sur une touche, et travailler sur la liste des nombres premiers trouvés qui est alors affichée.
De plus, tous les nombres premiers sauf 2 étant impairs, le programme met automatiquement 2 dans la liste au départ, et recherche ensuite les nombres premiers parmi les nombres impairs avec un pas de deux, pour plus de rapidité.
Je pense qu'il s'agit d'un des programmes les plus rapide que l'on peut réaliser en TI-Basic en se basant sur cet algorithme.
Sur TI-84+/83+SE, on obtient les 999 premiers nombres premiers en moins d'une 15aine de minutes.
La seule façon d'aller encore plus vite, serait de supprimer l'affichage au fur et à mesure des nombres trouvés, mais ce serait beaucoup moins amusant...
Malheureusement, le programme ne peut déterminer que les 999 premiers nombres premiers...
Le problème n'est pas du à une erreur de précision sur les 13 chiffres significatifs de la calculatrice...
Ni à une saturation de la mémoire par la "grosse" liste des nombres premiers...
J'avais prévu ces problèmes, mais...
Le problème est en fait bien plus bête et se produit hélas bien plus tôt: les calculatrices TI n'acceptent pas plus de 999 éléments dans les listes...
Pour aller au-delà, il faudrait utiliser plusieurs listes (ou une autre structure de données: chaîne, matrice...)
C'est possible, mais les instructions supplémentaires à insérer dans la boucle vont considérablement ralentir la recherche (qui n'en a pas besoin)...
Il me semblait inutile de rajouter des instructions pour aller au delà de 1000 nombres premiers, s'il fallait les attendre beaucoup plus longtemps.
Mais vous êtes libre de modifier ce programme comme bon vous semble.
[panneau]Informations techniques :
- Compatible avec : TI-76.fr / 82 Stats / 82 Stats.fr / 83 / 83 Plus / 84 Plus (testé)
- Incompatible avec : -
- ROMs supportées : toutes
- Bugs reportés : -[/panneau]
La complexité reste exponentielle (il ne faut pas attendre de miracle), mais je l'ai optimisé le plus que j'ai pu en mettant le moins d'instructions possibles dans la boucle.
Il est basé sur la condition nécessaire et suffisante suivante:
"un nombre n est premier" si et seulement si "il est divisible par tous les nombres premiers inférieurs à racine de n"
Le programme construit donc pas ordre croissant une liste des nombres premiers, et s'en sert au fur et à mesure pour trouver de plus grands nombres premiers.
A tout moment, vous pouvez arrêter le programme en tapant sur une touche, et travailler sur la liste des nombres premiers trouvés qui est alors affichée.
De plus, tous les nombres premiers sauf 2 étant impairs, le programme met automatiquement 2 dans la liste au départ, et recherche ensuite les nombres premiers parmi les nombres impairs avec un pas de deux, pour plus de rapidité.
Je pense qu'il s'agit d'un des programmes les plus rapide que l'on peut réaliser en TI-Basic en se basant sur cet algorithme.
Sur TI-84+/83+SE, on obtient les 999 premiers nombres premiers en moins d'une 15aine de minutes.
La seule façon d'aller encore plus vite, serait de supprimer l'affichage au fur et à mesure des nombres trouvés, mais ce serait beaucoup moins amusant...
Malheureusement, le programme ne peut déterminer que les 999 premiers nombres premiers...
Le problème n'est pas du à une erreur de précision sur les 13 chiffres significatifs de la calculatrice...
Ni à une saturation de la mémoire par la "grosse" liste des nombres premiers...
J'avais prévu ces problèmes, mais...
Le problème est en fait bien plus bête et se produit hélas bien plus tôt: les calculatrices TI n'acceptent pas plus de 999 éléments dans les listes...
Pour aller au-delà, il faudrait utiliser plusieurs listes (ou une autre structure de données: chaîne, matrice...)
C'est possible, mais les instructions supplémentaires à insérer dans la boucle vont considérablement ralentir la recherche (qui n'en a pas besoin)...
Il me semblait inutile de rajouter des instructions pour aller au delà de 1000 nombres premiers, s'il fallait les attendre beaucoup plus longtemps.
Mais vous êtes libre de modifier ce programme comme bon vous semble.
[panneau]Informations techniques :
- Compatible avec : TI-76.fr / 82 Stats / 82 Stats.fr / 83 / 83 Plus / 84 Plus (testé)
- Incompatible avec : -
- ROMs supportées : toutes
- Bugs reportés : -[/panneau]
