π
<-

fonction isprime et crible d'ératosthène

Pour le TI-Basic sur Nspire

fonction isprime et crible d'ératosthène

Bonjour
Je voulais savoir, si possible, si la fonction isprime(entier) est indépendante du crible d'ératosthène ou bien elle l'utilise ?
Merci pour le renseignement.

Niveau 9: IC (Compteur Infatigable)
Level up: 23.8%

Posts: 209
Joined: 29 Jan 2015, 19:32
Gender:
Class: etudiant

Re: fonction isprime et crible d'ératosthène

Pas de crible ("sieve" en anglais) : d'après http://www.technicalc.org/tiplist/en/fi ... ip6_55.pdf, des détails sur l'algo utilisé sur les TI-68k donc vraisemblablement la même chose sur TI-Nspire :

[6.55] Algorithms for factor() and isPrime()

The following description of the algorithms for factor() and isPrime() was obtained from TI by Bhuvanesh Bhatt. It is included with TI's permission.

TI wrote:The algorithms used in the TI-92, TI-92 Plus, and TI-89 are described in D. Knuth, The Art of Computer Programming, Vol 2, Addison-Wesley, but here is a brief description:

The TI-92 simply divides by successive primes through the largest one less than 2^16.1: It doesn't actually keep a table or use a sieve to create these divisors, but cyclically adds the sequence of
increments 2, 2, 4, 2, 4, 2, 4, 6, 2, 6 to generate these primes plus a few extra harmless composites.

TI-92 Plus and TI-89 start the same way, except that they stop this trial division after trial divisor 1021, then switch to a relatively fast Monte-Carlo test that determines whether the number is certainly composite or is almost certainly prime. (Even knowing the algorithm, I cannot construct a composite number that it would identify as almost certainly prime, and I believe that even centuries of continuous experiments with random inputs wouldn't produce such a number).

The isPrime() function stops at this point returning either false or (almost certainly) true.

If the number is identified as composite, the factor() function then proceeds to the Pollard Rho factorization algorithm. It is arguably the fastest algorithm for when the second largest prime factor has less than about 10 digits. There are faster algorithms for when this factor has more digits, but all known algorithms take expected time that grows exponentially with the number of digits. For example, the Pollard Rho algorithm would probably take centuries on any current computer to factor the product of two 50-digit primes. In contrast, the isPrime() function would quickly identify the number as composite.

Both the compositivity test and the Pollard Rho algorithm need to square numbers as large as their inputs, so they quit with a "Warning: ... Simplification might be incomplete." if their inputs exceed about 307 digits.

Niveau 16: CC2 (Commandeur des Calculatrices)
Level up: 50.2%

Posts: 12384
Images: 1079
Joined: 01 Jun 2007, 00:00
Location: France
Gender:
Calculator(s):
Class: (ingénieur)

Re: fonction isprime et crible d'ératosthène

Merci pour la lecture.
Je ne pensais pas qu'il y avait tous ces algorithmes et surtout ils peuvent mettre des siècles pour factoriser un entier produit de deux nombres premiers (50 chiffres chacun).
Mon petit programme est du niveau "primaire" juste pour générer les nombres premiers entre n et m.

Code: Select all
Define LibPub fpremiers(n,m)=Func:Local p:For p,n,m: If isPrime(p) Then:   Disp p: EndIf:EndFor:Return "ok":EndFunc

Niveau 9: IC (Compteur Infatigable)
Level up: 23.8%

Posts: 209
Joined: 29 Jan 2015, 19:32
Gender:
Class: etudiant

Re: fonction isprime et crible d'ératosthène

Il n'y a aucun rapport entre les 3 problèmes suivants :
1) Déterminer si un entier donné est premier ou non (ce que fait la fonction "isprime")
2) Déterminer la liste de tous les entiers premiers inférieurs ou égaux à un entier donné (ce que fait le crible d'Ératosthène)
3) Factoriser un entier donné.

Dans le premier cas, on connait des algorithmes très efficaces, capables de décider en quelques millièmes de secondes si des nombres de quelques centaines de chiffres sont premiers ou non.
Dans le 2ème cas, on ne connaît pas grand chose de mieux que le crible d'Ératosthène lui-même... mais il permet déjà d'établir une telle liste en quelques secondes pour des entiers ayant moins de 10 chiffres.
Dans le 3ème cas, on connaît plein d'algorithmes, la plupart étant plus ou moins efficaces suivant le champ d'application, c'est-à-dire suivant la forme des nombres auxquels on les applique. C'est un problème bien plus complexe que les deux précédents... et c'est justement sur le fait que ce soit complexe que se basent une grande partie des systèmes de cryptage.

Niveau 15: CC (Chevalier des Calculatrices)
Level up: 47.4%

Posts: 5419
Joined: 11 Mar 2008, 00:00
Location: Lyon
Gender:
Calculator(s):

Re: fonction isprime et crible d'ératosthène

Merci Bisam pour tes explications.
Donc il faudra que j'applique le crible d'Ératosthène pour être en "conformité"

Niveau 9: IC (Compteur Infatigable)
Level up: 23.8%

Posts: 209
Joined: 29 Jan 2015, 19:32
Gender:
Class: etudiant

Re: fonction isprime et crible d'ératosthène

Tu peux sans doute utiliser ta méthode pour de petites valeurs de n et m.
Tu peux simplifier ainsi :
Code: Select all
Define Libpub fpremiers(n, m)=FuncReturn delvoid(seq(when(isPrime(p),p,_),p,n,m))EndFunc

Niveau 15: CC (Chevalier des Calculatrices)
Level up: 47.4%

Posts: 5419
Joined: 11 Mar 2008, 00:00
Location: Lyon
Gender:
Calculator(s):

Who is online

Users browsing this forum: No registered users and 3 guests

-
Search
-
Featured topics
1234
-
For more contests, prizes, reviews, helping us pay the server and domains...

Discover the the advantages of a donor account !
JoinRejoignez the donors and/or premium!les donateurs et/ou premium !

-
Featured files

-
Stats.
423 utilisateurs:
>337 invités
>81 membres
>5 robots
Record simultané (sur 6 mois):
6892 utilisateurs (le 07/06/2017)
-
Other interesting websites
Texas Instruments Education
Global | France
(English / Français)
Banque de programmes TI
ticalc.org
(English)
La communauté TI-82
tout82.free.fr
(Français)