Déterminer le nième nombre premier.

[ggauny@live.fr]

PourTi.JPG (26.26 KiB) Viewed 1899 times

Bonjour,

Cherchant à "maîtriser" ma Ti_Nspire CX II T CAS, j'étudie le livret Ti-codes et je rencontre un problème :
au lieu de trouver 17573 comme indiqué sur l'exercice, j'obtiens 17161. Je n'ai aucune erreur dans la recopie du code Ti donné en exemple.
Si quelqu'un peut m'aider... merci d'avance.

[Afyu]

Bonjour,

À la ligne 5, la borne floor(sqrt(n)) n'est pas suffisante et doit être remplacée par floor(sqrt(n))+1 afin que la boucle for prenne les valeurs jusqu'à floor(sqrt(n)) inclus !

En insérant la ligne print(N,ep(N)) dans la boucle while, on constate que tous les entiers compris entre 3 et 9 inclus sont considérés comme premiers avant correction de l'erreur.

D'ailleurs, étant donné que l'on commence avec l'initialisation N=2, les lignes 3 et 4 if n<=1:return 0 deviennent inutiles. On ne vérifie la primalité qu'à partir de 3, finalement, puisque la boucle while commence par un N+=1 qui passe la valeur stockée dans la variable N à 3 et le premier test ep(N) est alors effectué avec N=3.

[critor]

Merci @Afyu.

Cela n'a pas l'air de déclencher de problème ici, mais le for k in range(2,floor(sqrt(n))) me semble également très maladroit.

La valeur retour de sqrt(n) est un flottant et donc une valeur pas forcément exacte, et le test d'arrêt de la boucle est donc une comparaison d'un entier à la partie entière d'un flottant possiblement approché.

[Afyu]

Merci @Afyu.

Cela n'a pas l'air de déclencher de problème ici, mais le for k in range(2,floor(sqrt(n))) me semble également très maladroit.

La valeur retour de sqrt(n) est un flottant et donc une valeur pas forcément exacte, et le test d'arrêt de la boucle est donc une comparaison d'un entier à la partie entière d'un flottant possiblement approché.

Tu veux dire, par exemple, que si la racine carrée de 9 est évaluée à 2.9999999996 alors comme la partie entière de cette estimation est 2, le dernier test effectué sera la division euclidienne de 9 par 2, qui donne un reste différent de 0. Le test de la division euclidienne de 9 par 3 (qui donne un reste nul, et indique donc que 9 n'est pas premier) n'étant pas effectué, le nombre 9 sera estimé comme étant premier, alors qu'il ne l'est pas.

On pourrait alors remplacer par for k in range(2,floor(sqrt(n))+2) afin d'être sûr de ne pas oublier une valeur à tester. Que proposes-tu, sinon ?

[ggauny@live.fr]

Je trouve 17497 au lieu des 17573 qui est le 2020ème nombre premier.
Pourtant j'ai bien corrigé comme vous me le dites.

Merci aussi Critor, je vais essayer +2.

Oui cela fonctionne, j'ai bien 17573. Il faudrait le dire à Ti peut-être ?

[critor]

Merci @Afyu.

Cela n'a pas l'air de déclencher de problème ici, mais le for k in range(2,floor(sqrt(n))) me semble également très maladroit.

La valeur retour de sqrt(n) est un flottant et donc une valeur pas forcément exacte, et le test d'arrêt de la boucle est donc une comparaison d'un entier à la partie entière d'un flottant possiblement approché.

Tu veux dire, par exemple, que si la racine carrée de 9 est évaluée à 2.9999999996 alors comme la partie entière de cette estimation est 2, le dernier test effectué sera la division euclidienne de 9 par 2, qui donne un reste différent de 0. Le test de la division euclidienne de 9 par 3 (qui donne un reste nul, et indique donc que 9 n'est pas premier) n'étant pas effectué, le nombre 9 sera estimé comme étant premier, alors qu'il ne l'est pas.

On pourrait alors remplacer par for k in range(2,floor(sqrt(n))+2) afin d'être sûr de ne pas oublier une valeur à tester. Que proposes-tu, sinon ?

Merci, oui c'est ce que je crains. Ta correction évite en effet le problème, mais aurait l'inconvénient de faire une itération supplémentaire bien souvent inutile.

Personnellement, je proposerais de rester sur des entiers et donc de passer à une boucle Tant que :
while(k**2 <= n):

[Bisam]

Une boucle "while" permet de rester dans les nombres entiers.
Deux possibilités :

Code: Select all

def ep(n):
    if n <= 1:
        return 0
    k = 2
    while k*k < n:
        if n%k == 0:
            return 0
        k += 1
    return 1

Cette possibilité oblige à calculer le carré de de k à chaque itération.
On peut remplacer cela par une addition de la façon suivante :

Code: Select all

def ep(n):
    if n <= 1:
        return 0
    k = 2
    k2 = 4
    while k2 < n:
        if n%k == 0:
            return 0
        k += 1
        k2 += 2*k + 1
    return 1

[EDIT] J'ai modifié les codes précédents suite à la remarque de Parisse un peu plus bas.

[Afyu]

On peut remplacer cela par une addition de la façon suivante :

Code: Select all

def ep(n):
    if n <= 1:
        return 0
    k = 2
    k2 = 4
    n2 = n*n # pour le calculer une seule fois
    while k2 < n2:
        if n%k == 0:
            return 0
        k += 1
        k2 += 2*k + 1
    return 1

Les lignes 10 et 11 doivent être interverties, non ?

[critor]

Merci beaucoup @Bisam pour cette nouvelle amélioration.

[Bisam]

Bonne remarque d'Afyu. Il faut soit intervertir les lignes 10 et 11, soit mettre un 2*k - 1 à la place du 2*k + 1.
Un peu trop de précipitation de ma part.